[백준] 1463번 - 1로 만들기 (실버 3)

문제

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

1463번: 1로 만들기

 

---

 

접근 방식

• 다이나믹 프로그래밍 분류에 있는 문제이므로 점화식을 찾아 DP로 구현

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

 

위 규칙을 기반으로 점화식을 찾아보자.

가능한 연산과 규칙을 나열해보면 최종적으로 dp[n] = 1 + min(dp[n-1], dp[n/2], dp[n/3]) 이라는 점화식을 찾을 수 있다. 점화식의 의미는 현재 수에 대한 연산 횟수 증가(1) + 가능한 이전 연산 중 최소 값 ( min(...) ) 이다.

 

---

 

코드

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    int min, num;

    cin >> num;

    int* dp = new int[num+2];
    memset(dp, 0, sizeof(int) * (num+2));
    
    for (int i = 2; i <= num; i++) {
        dp[i]++;
        min = 0;

        if (min > dp[i - 1] || min == 0)
            min = dp[i - 1];

        if (i % 2 == 0) {
            if (min > dp[i / 2])
                min = dp[i / 2];
        }

        if (i % 3 == 0) {
            if (min > dp[i / 3])
                min = dp[i / 3];
        }

        dp[i] += min;
    }

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

---

 

결과

 

​