1로 만들기

문제 정보

• 백준 실버 3
• DP
• 문제 링크

풀이

정수 N을 1로 만드는데 필요한 연산의 최소 횟수를 구하는 문제다.

dp[i]를 i가 1이 되도록 하는 연산의 최소 횟수로 정의한다.

나누어 떨어진다고 해서 무조건 나누는 게 능사는 아니다. 예를 들어 N = 10인 경우, 10 -> 9 -> 3 -> 1로 3이 최소이지만, 무조건 나눌 경우 10 -> 5 -> 4 -> 2 -> 1로 4가 출력되기 때문이다.

그렇기에 dp[i] = dp[i - 1] + 1을 대입하고, dp[i/3] + 1, dp[i/2] + 1과 비교했다. (다만 나누어 떨어질 때만 나누기 때문에 조건 검사 필요.)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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());
        
        if (n == 1) {
            System.out.println(0);
            return;
        } else if (n == 2 || n == 3) {
            System.out.println(1);
            return;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 0;
        dp[2] = dp[3] = 1;
        
        for(int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
        }
        
        System.out.println(dp[n]);
    }
}