[백준] 1463번

처음에는 문제에 적혀진 조건대로만 수행하려 했었다.

하지만 함정이 하나 있었으니.. 

함정

 

따라서 dp를 활용하여 문제를 해결했다.

 

dp를 구현할 때 for 문 안에 조건문을 다음처럼 구현하면 실패한다. (실패자 + 1)

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

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

2와 3의 최소공배수인 6으로도 나눠질 수 있기 때문이다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());    // 정수 N
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;

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

            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);
            }
        }
        System.out.println(dp[n]);
    }
}