[백준 / 파이썬] 1463번 1로 만들기

n = int(input())
a = [0] * (n+1) # n만큼 초기화

for i in range(2, n+1): # 1은 횟수가 0이니까 2부터 탐색
    a[i] = a[i-1] + 1 # 기본 값으로 이전 항의 연산 횟수 + 1

    if i % 2 == 0:
        a[i] = min(a[i], a[i//2] + 1)
    if i % 3 == 0:
        a[i] = min(a[i], a[i//3] + 1) # 미리 저장해 둔 값과 몫+1 한 값 중 더 작은 값

print(a[n])

 

DP문제로 작은 문제의 결괏값을 큰 문제에서도 활용하기

다이나믹 프로그래밍은 두 가지 방식이 있는데 보통 상향식 방식을 이용했을 때 성능이 좋다

상향식 방식은 메모이제이션 기법 활용 - 한 번 연산을 통한 결괏값을 메모리에 저장해 두고 같은 식의 연산을 재호출하면 메모리에 저장한 값을 불러와 활용

a = [0] * (n+1) 계산된 결과를 메모이제이션 하기 위해 리스트 초기화

 

예를 들어 12를 입력받았을 때 3으로 먼저 나눠준 경우를 생각한다면 4가 되는데 만약 [4가 1이 되는 최소 횟수]를 알고 있다면 그 최소 횟수 +1 이 된다

12를 2로 먼저 나눠주는 경우의 수를 생각할 때도 마찬가지고 6이 되고 [6이 1이 되는 최소 횟수] + 1이 된다

이런 식으로 작은 문제들을 반복해서 해결해나가야 한다