[백준] 1463 1로 만들기 풀이 Java

 

1463번: 1로 만들기

 

DP

 

문제

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

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

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

 

풀이

제출 했을 때 100%에서 틀렸다고 떠서 뭘 잘못했나 했더니 1일때 답은 0이라는 것을 놓쳤었다.

 

아래 코드를 보면 조건만 맞는다면 i-1, i%3, i%2에 대해서 모두 검사하게 되어있다.

그 이유는 아래와 같이 n=10 일 때, 다양하게 갈라질 수 있기 때문에 가장 작은 수를 찾기 위해 모두 다 검사한다.

1) i-1 : n(9)+1 = 3

2) i/2 : n(5)+1 = 4

 

 

 

import java.util.Scanner;

public class Main {
	static int[] dp;

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

		int n = scan.nextInt();
		dp = new int[n + 1];

		dp[1] = 0;
		for (int i = 2; i <= n; i++) {

			if (i <= 3)
				dp[i] = 1;
			else {
				dp[i] = dp[i - 1] + 1;

				if (i % 3 == 0) {
					dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
				}
				if (i % 2 == 0) {
					dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
				}
			}
		}
		System.out.println(dp[n]);
	}
}