[백준_1463번] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

[문제]

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

[입력 조건]

 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_1463 {
	public static int n;
	public static Integer[] dp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dp=new Integer[n+1];
		
		dp[0]=dp[1]=0;
		
		System.out.println(makeone(n));
	}
	public static int makeone(int n) {
		if(dp[n]==null) {
			// 6으로 나눠지는 경우
			if(n%6==0)
				dp[n]=Math.min(makeone(n/3), Math.min(makeone(n/2), makeone(n-1)))+1;
			// 3으로 나눠지는 경우
			else if(n%3==0)
				dp[n]=Math.min(makeone(n/3), makeone(n-1))+1;
			// 2로 나눠지는 경우
			else if(n%2==0)
				dp[n]=Math.min(makeone(n/2), makeone(n-1))+1;
			// 2와 3으로 나눠지지 않는 경우 -> -1을 하는 경우
			else 
				dp[n]=makeone(n-1)+1;
		}
		return dp[n];
	}
}

 

[구현]

 이번 문제는 2와 3의 최소 공배수인 6으로 나눠지는 경우에는 2로 나누는 경우 or 3으로 나누는 경우 or 1을 빼는 경우 모두를 고려해 최소 값을 택해야 한다는 점만 이해한다면 어려지 않게 풀 수 있는 문제였다.

 또한 이와 같은 문제를 그리디 알고리즘이 아닌 동적 계획법으로 풀어야 하는 이유는 n을 무조건 큰 수로 계속해서 나누는 값이 최솟값이 아니기 때문이다. 이렇게 문제를 해결하는 알고리즘을 선택할 때는 이유가 있다. 앞으로는 어떤 문제를 왜 이런 알고리즘으로 풀어야 하는지 타당한 근거를 갖고 고민해봐야 겠다는 생각을 했다.