[BOJ] 1463번 - 1로 만들기

<접근 방식>

DP를 이용한 문제로 점화식을 찾는 것이 매우 중요하다.

코드에서 선언한 dp 배열의 index가 숫자를 뜻하고 배열의 값은 해당 index까지 도달하는데 최소 경우의 수를 의미한다.

 

문제에서의 조건을 점화식으로 나타내었을 때

1) 3로 나누어 떨어진다 : dp[i] = dp[i/3] + 1

2) 2로 나누어 떨어진다 : dp[i] = dp[i/2] + 1

3) 1을 뺀다 : dp[i] = dp[i-1] + 1

 

위 경우를 비교하여 최소값을 넣어주면 된다.

<전체 코드>

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000001];

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

    
    int n;
    cin >> n;

    dp[1] = 0;

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

<문제 링크>

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

1463번: 1로 만들기