C++) [BOJ] 1463 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000001]; // dp[i]는 i를 1로 만드는데 필요한 최소 연산 횟수

int main()
{
    int n;
    cin >> n;

    dp[1] = 0; // 1을 1로 만드는데 필요한 연산 횟수는 0

    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + 1; // i에서 1을 빼는 경우
        if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1); // i가 2로 나누어 떨어지는 경우
        if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1); // i가 3으로 나누어 떨어지는 경우
    }

    cout << dp[n] << "\n";
    return 0;
}

 

DP(동적 프로그래밍)으로 접근하여 모든 상황에 대응할 수 있는 최저값을 구해야한다. 마치 수학 공식을 찾듯 생각해야하기 때문에 사고의 전환이 필요하다.