[Baekjoon] 1로 만들기 2

👀 문제 설명

문제

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

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

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

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

 

출력

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

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

 

예제 입력 1

2

 

예제 출력 1

1

2 1

 

예제 입력 2

10

 

예제 출력 2

3

10 9 3 1

 

✍🏻풀이

DP를 사용한다.

dp 배열은 N이 i일 때, 연산을 하는 횟수의 최솟값을 저장한다.

before 배열은 N이 i일 때, 직전 연산이 무슨 수인지 저장하는 배열이다.

즉, N이 9일 경우,

N	1	2	3	4	5	6	7	8	9
dp[N]	0	1	1	2	3	2	3	3	2

N	1	2	3	4	5	6	7	8	9
before	0	1	1	2	4	2	6	4	3

 

위와 같은 표가 나온다.

 

dp값을 구하기 위해서 i가 1부터 N까지 차례로 접근하고,

dp[i * 3] = dp[i * 2] = d[i + 1] = dp[i] + 1 이라는 공식을 사용해 구해줬다. (문제에는 / 3, / 2, - 1이지만 거꾸로 생각한 것)

이 때, dp값이 아직 방문하지 않았을 때, 위와 같이 dp값을 정하고, before[i * 3] = before[i * 2] = before[i + 1] = i로 정해줬는데, 

이렇게만 할 경우, N이 10일 때 10 -> 5 -> 4 -> 2 -> 1 이라는 결과가 나와서 틀리게 된다.

그렇기 때문에 dp값이 정해져 있어도 (이전값), 이전값에 비해 dp[i] + 1이 더 작으면 바꿔줘야 한다.

 

즉, if ( !dp[i * 3] || (dp[i * 3] > dp[i] + 1)) 이라는 if문을 작성해야 한다. (i * 2, i + 1도 마찬가지)

 

코드

이전 코드 (틀림)

//  1로 만들기 2 (https://www.acmicpc.net/problem/12852)

#include <iostream>

#define MAX 1000001

using namespace std;

int dp[MAX];
int before[MAX]; // 

int main() {
    int N;
    cin >> N;

    dp[1] = 0;
    for (int i = 1; i <= N; i++) {
        // 1. 
        if (i * 3 <= MAX) {
            if (!dp[i * 3]) {
                dp[i * 3] = dp[i] + 1;
                before[i * 3] = i;
            }
        }

        // 2.
        if (i * 2 <= MAX) {
            if (!dp[i * 2]) {
                dp[i * 2] = dp[i] + 1;
                before[i * 2] = i;
            }
        }
        
        // 3.
        if (i + 1 <= MAX) {
            if (!dp[i + 1]) {
                dp[i + 1] = dp[i] + 1;
                before[i + 1] = i;
            }
        }
    }

    cout << dp[N] << "\n";
    int curN = N;
    while (true) {
        if (N == 1) {
            cout << N << " ";
            break;
        }

        cout << N << " ";
        N = before[N];
    }

    return 0;
}

 

정답

//  1로 만들기 2 (https://www.acmicpc.net/problem/12852)

#include <iostream>

#define MAX 1000001

using namespace std;

int dp[MAX]; // 연산을 하는 횟수의 최솟값
int before[MAX]; // i로 오기 전에 어느 곳에 있었는지 저장하는 배열

int main() {
    int N;
    cin >> N;

    dp[1] = 0;
    for (int i = 1; i <= N; i++) {
        // 1. 
        if (i * 3 <= N) { // N까지만 해도 됨 (이전에는 MAX로 했었다..!)
            if (!dp[i * 3] || (dp[i * 3] > dp[i] + 1)) { // 아직 방문하지 않았거나 || 방문했는데 새로운 값이 더 작을 경우!
                dp[i * 3] = dp[i] + 1;
                before[i * 3] = i;
            }
        }

        // 2.
        if (i * 2 <= N) {
            if (!dp[i * 2] || (dp[i * 2] > dp[i] + 1)) {
                dp[i * 2] = dp[i] + 1;
                before[i * 2] = i;
            }
        }
        
        // 3.
        if (i + 1 <= N) {
            if (!dp[i + 1] || (dp[i + 1] > dp[i] + 1)) {
                dp[i + 1] = dp[i] + 1;
                before[i + 1] = i;
            }
        }
    }

    cout << dp[N] << "\n";
    int curN = N;
    while (true) {
        if (N == 1) {
            cout << N << " ";
            break;
        }

        cout << N << " ";
        N = before[N];
    }

    return 0;
}