BOJ 12852 - 1로 만들기 2 문제풀이

문제를 읽고 이해하기

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

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

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

입력

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

출력

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

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

재정의와 추상화

참고로 이 문제는 clang 컴파일러에서 실행할 경우 메모리 오류가 발생합니다..!

DP를 이용해 문제를 풀 수 있다. DP 구현부는 코드를 보면 이해할 수 있으므로 따로 설명하지 않고, 최소 연산으로 1을 만드는 데까지의 과정을 저장하는 방법에 대해서만 설명하겠다. (중요함)

그 과정은 procedure라는 이름의 배열에 저장하는데, 배열의 인덱스는 현재의 값을 의미하고, 그 배열의 값은 최소 연산을 구현하는 다음 값을 의미한다. 즉, 배열의 값은 (현재의 값 - 1), (현재의 값 / 2), (현재의 값 / 3) 중 하나가 된다.

그리고 DP의 전 과정을 끝낸 후, 최소 연산을 구현하는 과정을 모두 출력할 때, procedure[idx]를 출력하고 idx의 값을 procedure[idx]로 갱신하며 procedure[idx]가 1일 때까지 반복한다. 그 후 1을 출력해주면 끝!

코드 작성

#include <iostream>
using namespace std;

int dp[1000001];
int procedure[1000001];

int process(int start) {
    if (start == 1) { return 0; }

    auto & ref = dp[start];
    if (ref) return ref;

    ref = process(start - 1) + 1;
    procedure[start] = start - 1;
    if (start % 2 == 0) {
        int temp = process(start / 2) + 1;
        if (ref > temp) {
            ref = temp;
            procedure[start] = start / 2;
        }
    }
    if (start % 3 == 0) {
        int temp = process(start / 3) + 1;
        if (ref > temp) {
            ref = temp;
            procedure[start] = start / 3;
        }
    }
    return ref;
}

int main() {
    int n;
    cin >> n;
    cout << process(n) << '\n';
    cout << n << ' ';

    int idx = n;
    while (procedure[idx] != 1) {
        cout << procedure[idx] << ' ';
        idx = procedure[idx];
    }
    cout << 1;
    return 0;
}