[DP] 백준 1463 1로 만들기 C++

※ 문제

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

1463번: 1로 만들기

 

※ 풀이

동적계획법의 Bottom-Up방식으로 해결한다.

dp[i]:=i를 1로 만들기 위한 최소 연산 횟수

1) i가 1일 때, 연산하지 않는다. (dp[1] = 0)

2) i가 2일 때, 2로 나눈다. (dp[2] = 1)

3) i가 3일 때, 3으로 나누다. (dp[3] = 1)

4) i가 4이상 일 때,

 - 6으로 나누어지면 dp[i/2]와 dp[i/3] 중 최소 연산 횟수에 1을 더한다. (dp[i]=min(dp[i/2], dp[i/3])+1)

 - 3으로 나누어지면 dp[i/3]에 1을 더한다. (dp[i]=dp[i/3]+1)

 - 2로 나누어지면 dp[i/2]에 1을 더한다. (dp[i]=dp[i/2]+1)

#include<iostream>
#define MAX 1000001

using namespace std;

long long n, ans;
long long dp[MAX];

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

    cin >> n;

    dp[1] = 0; dp[2] = 1; dp[3] = 1;

    for (int i = 4; i <= n; i++) {
        dp[i] = MAX;

        if (i % 6 == 0) dp[i] = min(dp[i / 3], dp[i / 2]) + 1;
        else if ( i % 3 == 0 ) dp[i] = dp[i / 3] + 1;
        else if ( i % 2 == 0 ) dp[i] = dp[i / 2] + 1;
        
        dp[i] = min(dp[i], dp[i - 1] + 1);
    }
    
    cout << dp[n];
}