#1463번 1로 만들기 (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1000001];

int solve(int n){
    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1] + 1;
        if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1);
        if(i%2==0) dp[i] = min(dp[i],dp[i/2]+1);
    }
    return dp[n];
}

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

    int N = 0;
    cin >> N;

    dp[1] = 0, dp[0] = 0;
    cout << solve(N);

    return 0;
}

min기능은 구현하지 않고 STL을 사용했다. 

우선 단계별로 코드를 설명하다면 하단과 같다. 

 

1. dp[i] = dp[i-1] + 1; ---> -1을 실행해서 1로 만드는 경우

: 숫자 '4'를 예시로 들어보자. '4'를 1로 만드는 방법은 나누기 2를 두번 걸치면 된다. 

다른 방법으로도 1을 만들 수 있지만, 어찌되었건 공통적으로 토탈 과정은 '2'번을 거쳐서 1이 나온다. 

그 다음 번째 숫자인 '5'를 1로 만든다고 가정해보자.

2를 나누냐 3을 나누냐를 떠나서, 4를 1로 만드는 과정에서 +1을 더해주면 5가 나오기 때문이다. 

2. if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1); ---> 3을 나누어 1로 만드는 경우

: 바로 윗줄에서 가장 간단한 '1'을 빼는 방식을 시행했다. 

다음으로 해당 숫자가 3으로 나눠지는지 판단해본다. 

나눠지면 -1을 해서 얻는 결과 vs 숫자를 3으로 나눈 뒤 +1하는 결과를 따져서 최소값을 기입해준다. 

왜 dp[i/3] + 1인가? 이는 1번의 논리와 같다. 

(1) 3으로 나눈다는 1개의 과정을 추가하여

(2) 3으로 나눠버린다음

(3) 3으로 나눴을 때 나오는 값의 과정의 합을 그대로 더해주기 때문이다. 

 

3. if(i%2==0) dp[i] = min(dp[i],dp[i/2]+1); ---> 2를 나누어 1로 만드는 경우

이는 2번과 같은 논리이다. 

 

이렇게 3가지 과정을 비교해서 최소값이 출력되는 로직이 완성된다.