[BOJ/백준] 12852번: 1로 만들기 2 (c++)

12852번: 1로 만들기 2 Link

✨Problem

-> N이 주어지고 1로 만들기 위해 사용하는 연산 횟수를 구하는 문제이다.

➡️Solution

1. 1로 만들기 위한 방법은 여러가지이다. 근데 가장 적은 연산 횟수를 구하는 문제다.
2. 그러면 다시 생각해봤을 때 현재 1~n까지 현재 자신을 만들 수 있는 연산의 최솟값을 저장하는 배열을 만들면 되지 않을까 ? -> Dynamic Programming 이용
3. 과거에 구한 값을 이용하여 다음 연산횟수의 최솟값을 구한다.
4. 1부터 시작하여 bottom-up 방식을 이용 (3가지 연산을 진행)

Source Code

vector<pair<int, int>> minNum(int n){
    vector<pair<int, int>> dp(n+1, pair<int,int>(MAX,0)); // 첫번째는 연산횟수, 두번째는 전에 index
    dp[1].first = 0;
    dp[1].second = 0;

    for(int i=1; i<=n; i++){
        if(i*3 <= n && dp[i*3].first > dp[i].first+1){
            dp[i*3].first = dp[i].first+1;
            dp[i*3].second = i;
        }
        if(i*2 <= n && dp[i*2].first > dp[i].first+1){
            dp[i*2].first = dp[i].first+1;
            dp[i*2].second = i;
        }
        if(i+1<=n && dp[i+1].first > dp[i].first+1){
            dp[i+1].first = dp[i].first+1;
            dp[i+1].second = i;
        }
    }
    return dp;
}

• 1부터 시작하여 3가지 연산 진행 (3곱, 2곱, 더하기1)
• dp배열에 pair<int,int>를 이용하여 첫번째는 연산횟수, 두번째에는 전단계의 index를 저장한다.
• if(i*3 <= n && dp[i*3].first > dp[i].first+1) -> if문을 통해 현재 연산횟수가 저장된것보다 작은 경우에만 저장한다.
• dp[i*3].first = dp[i].first+1; dp[i*3].second = i; -> 연산횟수 & [i*3] index전에 위치한 index위치 저장하기

-> 이렇게 dp 배열을 return해서 출력하기 !

마무리

• dp는 많이 풀어보면 감이 오는 것 같다..
• 항상 현재 위치까지 올 가장 최대, 최소 값을 구한다고 생각하자! 이렇게 생각하면 DP인지 감이 오는 것 같다