[백준] 1463. 1로 만들기 - 파이썬

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

 

풀이 1

정말 단순하게 생각하면,

"당연히 3으로 나누는게 가장 빨리 숫자를 줄일 수 있고, 그 다음이 2로 나누는 거고, 그 다음에 1을 빼는 것을 택하는 게 제일 유리한 거 아닌가?" 라고 생각할 수 있다. (약간의 Greedy 느낌!)

그러나, 10의 Input 예시만 생각해 봐도, 위와 같은 알고리즘으로는

1. 10은 2로 나눠지므로, 10/2 = 5
2. 5는 3, 2로 나눠지지 않으므로, 5-1=4
3. 4는 2로 나눠지므로, 4/2 = 2
4. 2는 2로 나눠지므로, 2/2 = 1

로 4번의 연산만에 1이 된다.

 

그러나, 첫 번째 단계에서 1을 빼는 것을 택한다면,

1. 10 - 1 = 9
2. 9 / 3 = 3
3. 3 / 3 = 1

로 3번의 연산만에 1을 만들 수 있는 것을 볼 수 있다.

 

N = int(input())
cnt = 0
while N != 1:
    if N % 3 == 0:
        N /= 3
    elif N % 2 == 0:
        N /= 2
    else:
        N -= 1
    cnt += 1
 
print(cnt)

 

풀이 2

따라서, 모든 연산 단계마다 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우를 모두 확인해 봐야 한다.

이를 효율적으로 계산하려면.. DP겠죠?

 

Top-Down 방식으로 풀었더니 재귀 횟수 초과(Recursion Error / 메모리 초과)가 뜸.

 

import sys
sys.setrecursionlimit(10**6)
N = int(input())
cnt = 0
 
'''dp[n] = n에서 1을 만들 수 있는 최소의 연산 횟수 (memoization)'''
dp = dict([])
 
 
def dpdp(n):
    if n == 1:
        return 1
    elif dp.get(n, -1) != -1:
        return dp[n]
 
    a = n
    b = n
 
    if n % 3 == 0:
        a = dpdp(int(n/3))
    if n % 2 != 0:
        b = dpdp(int(n/2))
 
    dp[n] = 1 + min(a, b, dpdp(n-1))
    return dp[n]
 
 
print(dpdp(N))

 

풀이 3

그럼 Bottom-Up으로 풀죠 뭐

 

N = int(input())
cnt = 0
 
'''dp[n] = n에서 1을 만들 수 있는 최소의 연산 횟수 (memoization)'''
dp = dict([])
 
dp[1] = 0
n = 1
for i in range(1, N):
    dp[i+1] = min(dp.get(i+1, N), dp[i]+1)
    dp[i*2] = min(dp.get(i*2, N), dp[i]+1)
    dp[i*3] = min(dp.get(i*3, N), dp[i]+1)
 
print(dp[N])