백준 - DP (#1463)

https://www.acmicpc.net/problem/1463
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

Code 1

N = int(input())

counts = [0 for x in range(N+1)]

for i in range(2,N+1):
    counts[i] = counts[i-1] + 1
    if i%2 == 0 :
        counts[i] = min(counts[i], counts[i//2]+1)
    if i%3 == 0 :
        counts[i] = min(counts[i], counts[i//3]+1)
    
print(counts[N])

Code 2

counts = {1:0, 2:1}
def counter(n):
    if n in counts:
        return counts[n]
    m = 1+min(counter(n//2)+n%2, counter(n//3)+n%3)
    counts[n] = m
    return m

N = int(input())
print(counter(N))

참고
   동적계획법(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 푸는 방식의 알고리즘이다. 분할정복(Divide & Conquer)과 비슷하다. 하지만 둘은 문제를 나누는 방식이 다르다. 분할정복은 문제가 중복되지 않는 반면, 동적계획법은 문제가 중복될 수 있어 메모이제이션 기법을 사용한다는 차이가 있다.
   반복문을 사용한 Bottom-up 방식과 재귀를 이용한 Top-down 방식이 가능하다.
( Code 1 : Bottom-up, Code 2 : Top-down )
Code 1을 보면 시간복잡도는 O(N) 이며, Code 2 는 Code 1 과 다르게 N보다 작은 모든 값을 채울 필요가 없기 때문에 더 빠르게 답을 찾을 수 있다.