[백준] 12852번 : 1로 만들기 2 – JAVA [자바]

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

 

 

---

문제

 

 

---

해결 방법

 

이 문제는 DP 방법을 이용하여 해결할 수 있다. 

1. dp[i]를 i를 1로 만들기 위한 최소 연산 횟수 라고 정의한다.

2. 초기값을 설정한다: dp[1] = 0 (1은 연산 없이 1이므로 연산 횟수가 0)

3. dp[i] 값을 dp[i-1], dp[i/2], dp[i/3] 중 최소값 +1로 설정한다.

4. dp[n]을 통해 최소 연산 횟수를 구한 후, 역추적(backtracking)을 이용하여 경로를 출력한다.

 

 

---

코드 

 

import java.io.*;
import java.util.*;

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());
        StringBuilder sb = new StringBuilder();
        int[] dp = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 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);
        }
        
        sb.append(dp[n]).append("\n");
        
        // 역추적 (경로 출력)
        while (n > 0) {
            sb.append(n).append(" ");
            if (n == 1) break;
            if (n % 3 == 0 && dp[n / 3] == dp[n] - 1) {
                n /= 3;
            } else if (n % 2 == 0 && dp[n / 2] == dp[n] - 1) {
                n /= 2;
            } else {
                n -= 1;
            }
        }
        
        System.out.println(sb.toString().trim());
    }
}

 

 

---

코드 설명

1. 동적 계획법(DP) 배열을 활용

dp[i]를 i를 1로 만들기 위한 최소 연산 횟수로 정의한다.

dp[i] = dp[i-1] + 1을 기본값으로 설정하고, i가 2 또는 3으로 나누어 떨어지면 최소값을 갱신한다.

 

2. 역추적을 통한 경로 복원

dp[n]을 통해 최소 연산 횟수를 알 수 있다.

n에서 시작하여, dp[n] - 1이 되는 숫자로 이동하며 역추적한다.

3으로 나누는 것이 가능하면 먼저 시도하고, 그다음 2, 마지막으로 -1 연산을 수행한다.

---

시간 복잡도 분석

• dp 배열을 채우는 과정은 O(N)이다.
• 역추적 과정도 O(N)이다.
• 전체적으로 O(N) 으로 해결할 수 있어, N ≤ 1,000,000 범위에서 충분히 빠르게 실행된다.