[백준 문제] 1463번 1로 만들기 (파이썬)
문제풀이
- 최고 중요한 다이나믹 프로그래밍 문제
- 재귀함수로 푸는것보다 Bottom-Up으로 푸는것이 좋음
- 결국 Bottom-Up은 for문으로 문제를 처음부터 훑으면서 d[n]에 최소(min)수를 집어 넣는 방법
다이나믹 프로그래밍
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘(예:피보나치 수)
- Overlapping Subproblem(큰 문제와 작은 문제를 같은 방법으로 풀 수 있음), Optimal Substructure(문제의 정답을 작은 문제에서 풀 수 있음) 이 두가지를 만족해야함
# Top-Down(재귀 이용) : 재귀를 이용하게 되면 메모리 제한 때문에 메모리 초과가 되므로 Bottom-Up으로 푸는 것이 좋다.
def go(n):
if n == 1:
return 0
if d[n] > 0:
return d[n]
d[n] = go(n-1) + 1
if n%2 == 0:
temp = go(n//2) + 1 # 나누기(/)로 하면 소수 나와서 오류생김
if d[n] > temp:
d[n] = temp
if n%3 == 0:
temp = go(n//3) + 1
if d[n] > temp:
d[n] = temp
return d[n]
n = int(input())
d = [0]*(n+1)
print(go(n))
# Bottom-Up(For문 이용)
n = int(input())
d = [0]*(n+1)
d[1] = 0
for i in range(2, n+1):
d[i] = d[i-1] + 1
if i%2 == 0 and d[i] > d[i//2] + 1:
d[i] = d[i//2] + 1
if i%3 == 0 and d[i] > d[i//3] + 1:
d[i] = d[i//3] + 1
print(d[n])
