[백준 - 1463] 1로 만들기 - Python, C++

분류: DP, Memoization, 재귀, 탑다운, 바텀업 /

문제

문제 링크

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

풀이

- 하향식 방법(top-down) + DP(Memoization)

import sys

# n에서 1까지 가는데 필요한 연산의 수
def steps(dp, n):
    if dp[n] == -1:
        isEven = ((n & 1) == 0)
        isMultipleOfThree = (n % 3 == 0)
        if isEven and isMultipleOfThree:
            dp[n] = 1 + min(steps(dp, n//3), steps(dp, n//2))
        elif isEven:
            dp[n] = 1 + min(steps(dp, n//2), steps(dp, n-1))
        elif isMultipleOfThree:
            dp[n] = 1 + min(steps(dp, n//3), steps(dp, n-1))
        else:
            dp[n] = 1 + steps(dp, n-1)
    return dp[n]

if __name__ == '__main__':
    read = sys.stdin.readline
    N = int(read())
    dp = [-1] * (N+1) # 재귀 함수 중복 방지 다이나믹 프로그래밍
    dp[1] = 0 # 1에서 1가는 건 0, 나머지는 -1로 초기화
    print(steps(dp, N))

`steps` 함수는 n에서 1까지 가는데 필요한 최소 연산의 수를 반환합니다.

n=6으로 예를 들면, 6에서 1로 가는 모든 경로는 아래 세 가지 경로입니다.

1. 나누기 3(1번 연산)를 해 2로 간 후 2에서 1로 간다. => 1 + steps(2)
2. 나누기 2(2번 연산)을 해 3으로 간 후 3에서 1로 간다. => 1 + steps(3)
3. 빼기 1(3번 연산)을 해 5로 간 후 5에서 1로 간다. => 1 + steps(5)

6에서 1로 가는 최소 경로는 모든 경로 중 최소인 경로이므로 steps(6)은 steps(2)+1, steps(3)+1, steps(5)+1의 최솟값을 반환합니다. 재귀를 돌다 보면 같은 입력에 대해 steps를 중복으로 호출하게 됩니다. n이 커질수록 중복 호출은 지수적으로 증가합니다. 중복 호출을 방지하기 위해 steps(k)의 결과 값을 dp[k]에 저장하고 steps(k)가 실행되면 dp[k]를 확인합니다.(`Memoization`) dp[k]가 초기값 -1이라면 steps(k)가 실행된 적이 없다는 뜻입니다.

steps는 n부터 문제의 크기를 줄여가며 재귀호출해 n=1까지 내려갑니다. n=1에 도달하면 dp[1]이 -1이 아니므로 재귀호출을 멈추고 n에서 1까지 가는 경로의 k들에 대해 dp[k]값들을 채우며 콜스택을 따라 올라가 최종적으로 steps(n)을 반환합니다.

- 상향식 방법(Buttom-up)

import sys

if __name__ == '__main__':
    read = sys.stdin.readline
    N = int(read())
    dp = [0]*(N+1)
    for i in range(2,N+1): 
        x = dp[i-1]
        if i & 1 == 0:
            x = min(x, dp[i>>1])
        if i % 3 == 0:
            x = min(x, dp[i//3])
        dp[i] = x + 1
    print(dp[N])

`dp[k]`는 k에서 1까지 가는 연산의 최소 횟수를 의미합니다. 즉 답은 dp[N]이 됩니다.

dp[1]은 0이므로 2부터 N까지 올라가며 dp 리스트를 채워 마지막으로 dp[N]을 구합니다.

dp[i]는 dp[i-1], dp[i/2], dp[i/3]에서 갈 수 있습니다. 따라서 dp[i] = min(dp[i-1], dp[i/2], dp[i/3]) + 1입니다.

i가 2의 배수인지와 3의 배수인지를 고려해 최솟값을 계산합니다.

 

- C++

#include <iostream>
using namespace std;

int dp[1000001];
inline int min(int a, int b) {return a < b ? a : b;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int i=2; i<=N; i++) {
        dp[i] = dp[i-1];
        if((i % 3) == 0) dp[i] = min(dp[i], dp[i/3]);
        if((i & 1) == 0) dp[i] = min(dp[i], dp[i/2]);
        dp[i]++;
    }
    cout << dp[N];
}

#include <iostream>
using namespace std;

int step[1000001];
inline int min(int a, int b) {return a < b ? a : b;}

int getStep(int n) {
    if(step[n] || n == 1) return step[n];
    step[n] = getStep(n-1);
    if((n % 3) == 0) step[n] = min(step[n], getStep(n/3));
    if((n & 1) == 0) step[n] = min(step[n], getStep(n/2));
    return ++step[n];
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    cout << getStep(N);
}