백준 문제풀이 : (12852) 1로 만들기 2 - C/C++

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

 

시간 제한	메모리 제한	난이도	알고리즘 분류
0.5초	512 MB	Silver 1	다이나믹 프로그래밍

 

 

문제

 

 

풀이

0.5초의 시간제한이 있는 문제다. N의 범위는 1부터 10의 6승까지이므로 반복문 중첩을 피할 수 있는 방법으로 풀이를 생각해봐야 한다. 특정 숫자 N이 주워졌을 때 최단 횟수로 1로 만들어지는 과정을 직접 샤프로 써가며 정리해본다.

 

N = 10

10 → 9 → 3 → 1

 

N = 9

9 → 3 → 1 

 

N = 8

8 → 4 → 2 → 1

 

N = 7

7 → 6 → 3 → 1

 

(이하 생략..)

 

숫자 네 개를 정리했을 뿐인데도 벌써 규칙이 보인다. 예를 들어 10의 경우, N이 9인 경우에서 맨 앞에 10이 붙었을 뿐이다. 이처럼 각 숫자의 최단 횟수는, 이전 숫자(연산 전)에다가 1을 더한 값이라는 사실을 알 수 있다.

 

이전 값과 연결되는 결과이므로 다이나믹 프로그래밍을 사용해 해결한다. 

 

점화식을 정리하면 다음과 같다.

 

d[n] = min(d[n/3], d[n/2], d[n-1]) + 1   

*단, d[n/3]과 d[n/2]는 n이 각각 3과 2로 나누어 떨어지는 경우에만 해당한다.

 

만약 문제에서 요구하는 답이 단순히 숫자 N이 1로 만들어지는 최단 횟수였다면 위 점화식을 구현하여 쉽게 풀이할 수 있다. 하지만 문제에서는 N이 1이 되는 과정에 포함된 숫자를 출력하라는 요구도 포함되어있다. 

 

따라서 위 점화식을 그대로 사용하되, vector 이중배열을 사용해 각 숫자별로 '1이 되는 과정에서 거치는 숫자' 배열을 저장해준다. 이 방법으로 풀이했을 때 d[n]의 정의는 아래와 같다.

 

d[n] : 숫자 n이 1이 되는 과정에서 거치는 숫자 배열의 주소를 저장하고 있다.

 

숫자 n의 최단 횟수는 d[n]의 배열 사이즈를 출력하면 된다. 구현 코드에서는 d 배열을 result 배열로 대체하였다.

 

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> result;

int main() {
    int N;
    scanf("%d", &N);
    
    result.resize(N+1);
    
    result[1].push_back(1);
    for (int n=2 ; n<=N ; n++) {
        int min=result[n-1].size();
        result[n]=result[n-1];
        if (n%3==0) {
            if (result[n/3].size()<min) {
                min=result[n/3].size();
                result[n]=result[n/3];
            }
        }
        if (n%2==0) {
            if (result[n/2].size()<min) { 
                result[n]=result[n/2];
            }
        }
        
        result[n].push_back(n);
    }
    
    printf("%d\n", result[N].size()-1);
    for (int i=result[N].size()-1 ; i>=0 ; i--) {
        printf("%d ", result[N][i]);
    }
}

 

 

END.