[ Baekjoon : python ] 백준 2021 1로 만들기 - 다이나믹 프로그래밍 (재귀호출)

[  BAEKJOON ONLINE JUDGE  ] 2021 1로 만들기 _ Python 파이썬

 

" 문제 "

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

" 아이디어 "

 

 

이 문제는 큰 문제를 작은 문제로 쪼개어 푸는 다이나믹 프로그래밍 방식으로 해결할 수 있다.

따라서, 점화식을 D(n) 을 정의하고 문제를 작게 쪼개어 보자.

 

D(n) = n을 1로 만드는 최소 횟수

 

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

-> D(n) = 1 + D(n/3)

 

2. X가 2로 나누어 떨어지면, 2로 나눈다.

-> D(n) = 1 + D(n/2)

 

3. 1을 뺀다.

-> D(n) = 1 + D(n-1)

 

이 모든 것을 종합해서 점화식을 정의하면

 

D(n) = min( D(n/3), D(n/2), D(n-1) ) + 1 (n>=2) D(n) = 0 ( n=1 ) <- 가장 작은 크기의 문제 (더 이상 쪼갤 수 없는 경우) 1을 1로 만드는 경우는 연산이 0번 필요하므로

 

---

" 코드 "

 

★ python으로 다이나믹 프로그래밍 문제를 풀 때 주의할 점 ★

1. top-down 방식의 경우 재귀의 깊이가 너무 깊이 들어가면 stackoverflow가 발생하기 때문에 재귀의 깊이를 제한해준다.

2. 이 문제의 경우 top-down 방식은 메모리 초과가 발생하므로 bottom-up 방식을 사용한다.

(다른 언어는 해당사항 없음)

 

 

n = int(input())
 
# memoizaion
m = [0]*(n+1)
 
# Bottom-Up 
m[1] = 0 # d(1) = 0
 
for i in range(2, n+1):
  m[i] = m[i-1] + 1 # (3)번
  if i%2 == 0 and m[i] > m[i//2] + 1: # (1)번
    m[i] = m[i//2] + 1
  if i%3 == 0 and m[i] > m[i//3] + 1: # (2)번
    m[i] = m[i//3] + 1
print(m[n])

 

---

" 참고자료 "