BOJ 1463 1로 만들기 python

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

 

dp(dynamic programming, 동적 계획법) 문제에 입문하면서 풀어본 첫 문제!

동적 계획법이란 -> 메모리를 조금 더 써서 속도를 크게 향상시키는 풀이법!

동적 계획법은 Top down 방식과 Bottom Up 방식으로 나뉜다.

이 중 Top down 방식은 재귀적으로 구현하기에 시스템의 스택 부하를 고려하면... 조금 부담스러울 수 있다.

그래서 Bottom Up 방식이 권장된다. 그리고 구현도 더 쉽다.

동적 계획법을 쓰는 상황 -> 문제를 봤는데, 큰 문제를 작은 문제들로 쪼갤 수 있으며 작은 문제의 답을 반복적으로 사용할 수 있으면 동적계획법!!

또한 동적 계획법으로 문제를 해결할 때는 각 항들의 관계에 대한 점화식을 작성해야 한다.

 

<문제 해결>

n = int(input())
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 0

for i in range(2, n+1):
    if i % 6 == 0:
        dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1
    elif i % 2 == 0:
        dp[i] = min(dp[i//2], dp[i-1]) + 1
    elif i % 3 == 0:
        dp[i] = min(dp[i//3], dp[i-1]) + 1
    else:
        dp[i] = dp[i-1] + 1

print(dp[n])

 

이 문제를 dp로 해결해야겠다고 생각한 이유:

1. 탐욕법으로 문제를 풀기에는 n이 커질 수록 연산량이 너무 많아진다.

2. 연산량이 많아지는 이유는 중복된 계산이 많기 때문이다.

3. 그렇다면 메모리를 사용해서 중복된 계산결과를 저장하면 된다!

 

dp[n]은 n을 1로 만들기 위해 최소한으로 필요한 연산 횟수를 의미한다.

특이사항은, n이 2와 3 둘 다로 나누어 떨어진다면 n//2, n//3, n-1 셋을 다 살펴보고 최솟값을 선택해야 한다.

예를 들어, dp[12] 는 dp[6]과 dp[4], 그리고 dp[11] 중 제일 작은 것에 1을 더해 주는 식으로 정해진다.

1을 더해주는 이유는, dp[6]이나 dp[4], dp[11]에 2를 곱하거나 3을 곱하거나 1을 더하는 한 번의 연산으로 12를 만들 수 있기 때문이다.

 

점화식은 다음과 같다!