다이나믹 프로그래밍 - 백준 1463 [Python]

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
• 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
  1. Overlapping Subproblem
  2. Optimal Substructure
• 모든 문제를 풀어야 하고, 모든 문제는 1번만 풀어야 한다는 것을 생각하고 해결해야 한다. 따라서 시간 복잡도는 문제의 개수 * 문제 1개를 푸는 시간이 된다.
• 구현에는 Top-down (재귀), Bottom-up (반복문) 방식으로 구성되어 있다.
• 점화식을 구성한 다음 문제를 작게 만들 수 있는 방법을 찾아야 한다.

Problem)

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

1463번: 1로 만들기

 

Solution)

D[N] = N을 1로 만드는 최소 연산 횟수

따라서

D[N] = min( D[N/3],  D[N/2],  D[N-1] ) + 1 이 들어가면 된다.

 

Answer)

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])