[백준 1463번] 1로 만들기 (C++, Python)

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

 

이번 포스트에서는 백준 알고리즘 문제인 1로 만들기 를 포스트하겠습니다.

 

해당 문제는 solved.ac 기준 실버 3에 위치한 문제입니다.

 

먼저 문제입니다.

문제에서 주어진 연산 3가지를 사용할 때, 정수 N을 입력받고 연산 3개를 골라서 사용했을 때, 가장 적은 횟수의 연산 횟수를 찾아서 출력하는 문제입니다.

 

해당 문제에서는 입력이 1인 경우는 0으로 알고 있는 값이기 때문에 2부터 시작해서 바텀업으로 해결하는 DP 알고리즘으로 해결할 수 있습니다.

 

N이 10으로 주어졌을 때, 10 -> 9 -> 3 -> 1 이 가장 적은 연산을 수행하는 방법입니다.

이때 N이 9일때도 9 -> 3 -> 1 이 가장 빠른 순서입니다.

또 다시 N이 3일때도 3 -> 1 이 가장 빠른 순서입니다.

 

위 예시로 볼때, N의 최소 연산 횟수는 앞에서 구한 결과 값에 + 1을 한 결과입니다.

 

그러므로 첫번째 연산인 1을 빼는 연산을 하면, dp[N] = dp[N - 1] + 1 로 정의됩니다.

이때, 현재 N이 2로 나누어 떨어진다면, dp[N]과 dp[N / 2] + 1 중 더 작은 값을 선택하여 dp[N]에 대입합니다.

N이 3으로 나누어 떨어지는 경우도 마찬가지로 dp[N]과 dp[N / 3] + 1 중 더 작은 값을 선택하여 dp[N]에 대입합니다.

 

점화식이 위 처럼 구해졌다면 코드 작성은 수월해집니다.

 

먼저 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int dp[1000001] = {0,};
 
int main() {
    int n;
    
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if(i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);
        if(i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);
    }
 
    cout << dp[n];
    return 0;
}

다음은 Python 코드입니다.

 

dp = [0] * 1000001
 
n = int(input())
 
for i in range(2, n+1) :
    dp[i] = dp[i - 1] + 1
 
    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0 :
        dp[i] = min(dp[i], dp[i // 3] + 1)
 
print(dp[n])

점화식을 빨리 찾는다면 쉬운 문제이지만, 저는 점화식을 찾는게 아직 어려워서 쉽지 않았던 문제였습니다..

 

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스팅하겠습니다. 감사합니다.