[백준/Baekjoon] 12852 1로 만들기 2 C++ :: Dynamic Programming

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

12852번: 1로 만들기 2

---

1. Logic

1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다.

2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다.

 

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
const int INF = 987654321;

int dp[1000001];
int before[1000001];

bool check = false;

int solve(int num) {
    int &ret = dp[num];
    if(num == 1) return 0;
    if(ret != -1) return ret;

    ret = INF;
    
    int next = solve(num - 1) + 1;
    if(next < ret) {
        ret = next;
        before[num] = num - 1;
    }

    if(num % 3 == 0) {
        int next = solve(num / 3) + 1;
        if(next < ret) {
            ret = next;
            before[num] = num / 3;
        }
    }

    if(num % 2 == 0) {
        int next = solve(num / 2) + 1;
        if(next < ret) {
            ret = next;
            before[num] = num / 2;
        }
    }
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset(dp, -1, sizeof(dp));
    memset(before, 0, sizeof(before));

    cin >> n;

    cout << solve(n) << "\n";

    while(n != 0) {
        cout << n << " ";
        n = before[n];
    }
}

 

 

---

 

 

3. Feedback

- 계산한 횟수를 재귀적으로 구하고 싶을때 : ret = min(ret, solve(다음 숫자) + 1) 이렇게 넣어주면 계산횟수를 구할 수 있다. 이때 기저조건은 (idx == 원하는 숫자) return 0;