(C++) - 백준(BOJ) 12852번 : 1로 만들기 2 답

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

bottom up dp로 풀었습니다.

 

 

풀이방법

 1. 1로 시작하여 n을 만드는 것으로 생각했습니다. 따라서 문제의 해당 조건에서 반대로 다음 수를 만들게 됩니다.

즉, 1을 빼는 것은 1을 더하는 것, 나누기 2하는 것은 2를 곱하는 것, 나누기 3하는 것은 3을 곱하는 것이 되게 됩니다.

 

 

이 때 3가지의 경우로 수를 만들 수 있습니다.

  1) 1을 더하는 것

      i + 1이라는 숫자를 만드는 방법의 수 = i라는 수를 만드는 방법 개수 + 1

  2) 2를 곱하는 것

      i * 2 이라는 숫자를 만드는 방법의 수 = i라는 수를 만드는 방법 개수 + 1

  3) 2를 곱하는 것

      i * 3 이라는 숫자를 만드는 방법의 수 = i라는 수를 만드는 방법 개수 + 1

 

1) ~ 3) 방법 중 한개를 선택했을 경우 해당 수를 저장해줍니다.

 

2. d[n]을 출력 후 저장된 수들을 모두 출력해줍니다.

 

Code

#include <bits/stdc++.h>
#define BIG 0x3f3f3f3f
using namespace std;

int d[1000001], arr[1000001];
int n;

int main(void) {
    cin >> n;
	fill(d,d+n+1,BIG);
    d[1] = 0;
    for(int i = 1; i <= n; i++){
        if(i+1 <= n && d[i+1] > d[i] + 1){
            d[i+1] = d[i] + 1;
            arr[i+1] = i;
        }

        if(i * 2 <= n && d[i*2] > d[i] + 1){
            d[i*2] = d[i] + 1;
            arr[i*2] = i;
        }

        if(i * 3 <= n && d[i*3] > d[i] + 1){
            d[i*3] = d[i] + 1;
            arr[i*3] =i;
        }
    }
    cout << d[n] << '\n';
    while(n){
        cout << n << ' ';
        n = arr[n];
    }
}