[백준 1463] 1로 만들기
1463번 : 1로 만들기
방법 1 (틀림)
- want: 연산 횟수의 최솟값
- 그리디 알고리즘 냄새가 나지만… 규칙에서 예외적인 경우가 있음 (그리디라면 최대한 큰 수로 나누었을 것)
=> 다양한 경우로 접근해서 최솟값을 따져봐야 함 (다이나믹 프로그래밍)
import sys
input = sys.stdin.readline
n = int(input())
cnt = 0
# 3으로 나눠 떨어지게 n-- 수행
while n > 3 and n % 3 != 0:
n -= 1
cnt += 1
# 최대한 3으로 나누기
while n % 3 == 0:
n //= 3
cnt += 1
# 2로 나눠 떨어지게 n-- 수행
while n > 1 and n % 2 != 0:
n -= 1
cnt += 1
# 최대한 2로 나누기
while n > 1:
n //= 2
cnt += 1
# n이 1이 될 때까지
while n!= 1:
n -= 1
cnt += 1
print(cnt)
방법 2 (옳은 풀이)
- 다이나믹 프로그래밍 - 메모이제이션을 활용해 불필요한 중복 계산을 막아준다
- Bottum Up 방식
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (n + 1) # 1번 idx부터 유의미한 값 다룸
for i in range(2, n+1):
dp[i] = dp[i-1] + 1
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
print(dp[n])