[JAVA] 백준 (실버1) 12852번 1로 만들기 2

링크

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

---

문제 설명

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

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

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

---

입력 예제

10

---

출력 예제

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

3
10 9 3 1

---

풀이

dp배열을 다음과 같이 정의한다.

dp[i]: i를 1로 만드는 방법의 최솟값

이 문제는 방법의 최솟값만 구하는게 아니라 1로 만드는 경로까지 구해야 하므로 경로를 저장할 path배열도 생성한다. 배열의 각 원소는 그 수를 1로 만들기 위한 연산의 결과값을 저장한다. N이 10으로 주어질 때 10 -> 9 -> 3 -> 1 순으로 연산을 진행되므로 path[10] = 9, path[9] = 3, path[3] = 1이 된다.

이를 Bottom-Up 방식으로 구현하면 다음과 같다.

for (int i = 2; i <= N; i++) {
    //기본적으로 1을 뺀다
    dp[i] = dp[i - 1] + 1;
    path[i] = i - 1;
    
    //3으로 나누어 떨어질 때 1을 뺄 때와 비교
    if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
        dp[i] = dp[i / 3] + 1;
        path[i] = i / 3;
    }
    
    //2로 나누어 떨어질 때 1을 뺄 때와 비교
    if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
        dp[i] = dp[i / 2] + 1;
        path[i] = i / 2;
    }
}

그리고 경로를 출력할 때는 다음과 같이 각 원소를 인덱스로 갱신하며 저장한다.

while (N > 0) {
    sb.append(N).append(" ");
    N = path[N];
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        int[] path = new int[N + 1];  //경로 저장

        for (int i = 2; i <= N; i++) {
            //기본적으로 1을 뺀다
            dp[i] = dp[i - 1] + 1;
            path[i] = i - 1;

            //3으로 나누어 떨어질 때 1을 뺄 때와 비교
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
                path[i] = i / 3;
            }

            //2로 나누어 떨어질 때 1을 뺄 때와 비교
            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
                dp[i] = dp[i / 2] + 1;
                path[i] = i / 2;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(dp[N]).append("\n");

        //경로를 따라가며 1이될 때까지 저장한다
        while (N > 0) {
            sb.append(N).append(" ");
            N = path[N];
        }

        System.out.println(sb);
    }
}