[BJ] 백준 11463 1로 만들기(JAVA)

문제

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

 

풀이 방법

문제는 간단하다. 
1. x가 3으로 나누어떨어지면, 3으로 나누기
2. x가 2로 나우어 떨어지면, 2로 나누기
3. 1를 빼기
위 세개의 연산을 적절히 사용해서 1을 만드는데 연산을 사용하는 횟수의 최소값을 구하는 문제이다.
이 문제는 dp를 사용해서 풀면 된다.
dp[N]에는 N이 1이 될때까지의 최소 연산 횟수를 가지고 있다. 
우선 N이 2또는 3으로 나누어떨어지는지 확인한다. 만약 나누어 떨어진다면 2로 나눴을 때와 3으로 나눴을때 어떤 수가 더 최소연산 횟수를 가지는지 비교해서 더 작은 값을 dp에 넣는다. 
그리고 항상 -1를 했을 경우의 연산의 최소값을 구해서 기존의 dp값과 비교 후, 더 작은 값을 dp에 넣어준다.
정리하면,
1. 2로 나눠지면 2로 나눈 후 최소 연산 횟수를 기존의 dp값과 비교  후 더 작은 값을 넣는다.
2. 3으로 나눠지면 3으로 나눈 후 최소 연산 횟수를 기존의 dp값과 비교  후 더 작은 값을 넣는다.
3. (항상) 1를 뺐을 때 최소 연산 횟수를 기존의 dp값과 비교  후 더 작은 값을 넣는다.

 

제출 코드

package D0225;

import java.util.Arrays;
import java.util.Scanner;

public class BJ_1463_1로만들기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] dp = new int[N + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);

		dp[1] = 0;
		for (int i = 2; i <= N; i++) {
			if (i % 2 == 0 || i % 3 == 0) {
				if (i % 2 == 0)
					dp[i] = Math.min(dp[i], dp[i / 2] + 1);
				if (i % 3 == 0)
					dp[i] = Math.min(dp[i], dp[i / 3] + 1);
			}
			dp[i] = Math.min(dp[i], dp[i - 1] + 1);
		}
		System.out.println(dp[N]);
	}

}