[백준 / Java] 12852: 1로 만들기 2 (DP)

난이도: Silver 1

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

 

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

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

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

 

아래 링크에 있는 문제를 응용한 문제이다.

이 문제를 먼저 풀어보고 해당 문제를 풀면 좀 더 쉽게 풀 수 있을 것이다.

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

 

위 링크에 있는 문제에서 연산을 하는 횟수의 최솟값을 구하려면 int 타입의 1차원 dp 배열을 만들어서 저장하고, 가장 큰 값을 출력하면 됐었다.

하지만 이번에는 N을 1로 만드는 방법에 포함되어 있는 수도 일일히 다 구해야 한다.

그러려면 int 타입의 정수만 저장하는 배열로는 부족하다. 클래스를 따로 만들어서 클래스 타입의 배열을 만들어야 한다.

 

클래스를 어떻게 만들지 설명하기 전에, 코드의 로직부터 먼저 설명하겠다.

 

 

입력받은 수를 10이라고 가정하고, 배열은 맨 처음에 인덱스가 1~10까지 0으로 초기화되어있다고 하자.

여기서는 1을 빼거나, 2로 나누어 떨어질 때 2로 나누거나, 3으로 나누어 떨어질 때 3으로 나누라고 했다.

10부터 검사할 것이다.

 

 

10에서 1을 뺀 9에 1(0 + 1)을 할당

10에서 2를 나눈 5에 1(0 + 1)을 할당

 

배열 값이 1인 곳을 기준으로 계속 진행해보자.

 

 

9에서 1을 뺀 8에 2(1 + 1)를 할당

9에서 3을 나눈 3에 2(1 + 1)를 할당

5에서 1을 뺀 4에 2(1 + 1)를 할당

 

배열 값이 2인 곳을 기준으로 계속 진행해보자.

 

 

8에서 1을 뺀 7에 3(2 + 1)를 할당

8에서 2를 나눈 4에 3(2 + 1)을 할당하려고 했으나, 원래 4에 있던 값이 2라서 더 작으므로 갱신 X

4에서 1을 뺀 3에 3(2 + 1)을 할당하려고 했으나, 원래 3에 있던 값이 2라서 더 작으므로 갱신 X

4에서 2를 나누거나, 3에서 1을 뺀 2에 3(2 + 1)을 할당

3에서 3을 나눈 1에 3(2 + 1)을 할당

 

배열 값이 3인 곳을 기준으로 계속 진행해보자.

 

 

7에서 1을 뺀 6에 4(3 + 1)을 할당

2에서 1을 빼거나, 2를 나눈 1에 4(3 + 1)을 할당하려고 했으나, 원래 1에 있던 값이 3이라서 더 작으므로 갱신 X

 

 

이제 맨 끝 인덱스만 제외한 모든 배열이 다 0이 아닌 값으로 채워졌으므로 끝났다.

사실 코드에서는 맨 끝부터 1까지 역순으로 for문을 돌리므로 실제 과정과는 조금 차이가 있지만, 일단 이런 로직이다.

 

연산을 하는 횟수의 최솟값을 출력할 때는 맨 처음 인덱스(1)에 있는 값인 3을 출력하면 된다.

문제는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력하는 것이다.

어떻게 해야 할까?

 

 

우선 맨 처음에는 무조건 1

1은 3 / 3으로 만들어졌으므로 3

3은 9 / 3으로 만들어졌으므로 9

9는 10 - 1로 만들어졌으므로 10

이것을 역순으로 출력하면 10 9 3 1

 

이렇게 구하기 위해서는 연산 정보도 저장해야 한다.

하지만 하나의 int 배열만으로는 연산 횟수만 저장할 수 있고, 연산 정보까지는 저장할 수 없다.

int 배열은 배열 하나 당 int 형의 정수만 저장할 수 있기 때문이다.

배열에 여러 값을 저장하기 위해서는 직접 클래스를 만들어서 그 클래스 타입으로 배열을 만들면 된다.

 

 

    // 숫자 클래스

    static class Num {

        int count;      // 현재 숫자를 만들기까지의 연산을 하는 횟수

        int before;     // 현재 숫자를 만든 바로 이전 숫자

       

        Num(int count, int before) {

            this.count = count;

            this.before = before;

        }

    }

 

 

다음과 같이 클래스를 만들어서, 이 클래스(Num) 타입의 배열을 선언한다.

Num 타입의 배열에 count와 before는 어떻게 매칭시킬까?

 

Num 클래스의 count(현재 숫자를 만들기까지의 연산을 하는 횟수)에는 배열에 담긴 값을 저장하면 되고,

Num 클래스의 before(현재 숫자를 만든 바로 이전 숫자)에는 갈색 네모에 있는 값, 즉 연산자 왼쪽에 있는 값들을 저장하면 된다.

이 배열을 채우는 과정은 위에 설명한 과정과 똑같다.

 

 

주석에 설명도 한 줄 한 줄 자세히 적어 놓았다.

자, 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
 
public class P12852_1로만들기2 {
    // 숫자 클래스
    static class Num {
        int count;        // 현재 숫자를 만들기까지의 연산을 하는 횟수
        int before;        // 현재 숫자를 만든 바로 이전 숫자
        
        Num(int count, int before) {
            this.count = count;
            this.before = before;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    // 입력받는 자연수
        Num[] dp = new Num[N + 1];    // 위에 만든 클래스 타입의 1차원 dp 배열
        
        // 입력받는 자연수(N)의 count: N은 맨 처음 숫자이므로 N을 만들기까지의 연산을 하는 횟수는 0
        // 입력받는 자연수(N)의 before: N을 만든 바로 이전 숫자는 없으므로 그냥 N으로 설정
        dp[N] = new Num(0, N);     
        
        // N부터 1까지 역순으로 검사
        for (int i = N; i >= 1; i--) {
            // 현재 숫자(i)보다 1 작은 숫자(i - 1)에 Num 객체가 없다면 새로 만들어주기
            if (dp[i - 1] == null) {    
                // i - 1의 count: i를 만들기까지의 연산 count 에서 1 증가
                // i - 1의 before: i - 1을 만든 바로 이전 숫자는 i
                dp[i - 1] = new Num(dp[i].count + 1, i);     
            } else if (dp[i].count + 1 < dp[i - 1].count) {
                // i의 count에서 1 더한 값이 i - 1의 원래 count보다 작다면 
                dp[i - 1].count = dp[i].count + 1;    // 더 작은 값으로 count 갱신
                dp[i - 1].before = i;                // i - 1을 만든 바로 이전 숫자를 i로 갱신
            }
            
            if (i % 2 == 0) {    // 현재 숫자(i)가 2로 나누어 떨어지면
                // 현재 숫자(i) 나누기 2(i / 2)에 Num 객체가 없다면 새로 만들어주기
                if (dp[i / 2] == null) {    
                    // i / 2의 count: i를 만들기까지의 연산 count 에서 1 증가
                    // i / 2의 before: i / 2를 만든 바로 이전 숫자는 i
                    dp[i / 2] = new Num(dp[i].count + 1, i);
                } else if (dp[i].count + 1 < dp[i / 2].count) {
                    // i의 count에서 1 더한 값이 i / 2의 원래 count보다 작다면 
                    dp[i / 2].count = dp[i].count + 1;    // 더 작은 값으로 count 갱신
                    dp[i / 2].before = i;                // i / 2를 만든 바로 이전 숫자를 i로 갱신
                }
            }
            
            if (i % 3 == 0) {    // 현재 숫자(i)가 3으로 나누어 떨어지면
                // 현재 숫자(i) 나누기 3(i / 3)에 Num 객체가 없다면 새로 만들어주기
                if (dp[i / 3] == null) {
                    // i / 3의 count: i를 만들기까지의 연산 count 에서 1 증가
                    // i / 3의 before: i / 3을 만든 바로 이전 숫자는 i
                    dp[i / 3] = new Num(dp[i].count + 1, i);
                } else if (dp[i].count + 1 < dp[i / 3].count) {
                    // i의 count에서 1 더한 값이 i / 3의 원래 count보다 작다면 
                    dp[i / 3].count = dp[i].count + 1;    // 더 작은 값으로 count 갱신
                    dp[i / 3].before = i;                // i / 3을 만든 바로 이전 숫자를 i로 갱신
                }
            }
        }
        
        // N을 1로 만드는 방법에 포함되어 있는 수 리스트
        ArrayList<Integer> nums = new ArrayList<>();    
        nums.add(1);    // 마지막엔 항상 1이 되므로 1을 우선 삽입
 
        int n = 1;        // 반복할 변수: 1부터 탐색
        
        // n(반복할 변수)이 맨 처음 입력받은 수(N)보다 작을 때까지 반복
        while (n < N) {    
            nums.add(dp[n].before);    // 현재 숫자를 만든 바로 이전 숫자를 리스트에 삽입
            n = dp[n].before;        // 현재 숫자를 만든 바로 이전 숫자를 n(반복할 변수)으로 갱신
        }
        
        bw.write(dp[1].count + "\n");    // N을 1로 만드는 연산을 하는 횟수의 최솟값 출력
        
        // N을 1로 만드는 방법에 포함되어 있는 수를 역순으로 출력
        for (int i = nums.size() - 1; i >= 0; i--) {
            bw.write(nums.get(i) + " ");
        }
        
        bw.flush();        // bw.write()로 버퍼에 쌓았던 문자열들을 한 번에 쓰기 => 속도 더 빠름
    }
}