[백준 1463] 1로 만들기(파이썬)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

• 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

---

DP 문제를 풀이하면서 이해가 잘 가지 않는 부분이 있어 정리해보았다.

 

DP란

• 문제를 더 작은 단위의 문제들로 나눈다.
• 작게 나누어진 문제들의 풀이들을 재귀적인 방식으로 최적화 솔루션을 찾음
• Tree 형태의 탐색 방식이라고 보아도 무방
• 모든 상태에 대해 최적의 결과를 모두 어딘가에 ‘저장’ 하고 있다는 사실도 잊지 말자.
• 즉 모든 경우를 수를 순차적으로 고려하는 방식이다

 

10을 예시로 들면 10 -> 9 -> 3 -> 1로 총 3번이면 1로 만들 수 있다.

10에서 1을 뺐을 경우 9가 된다. 여기서 우리가 만약 9가 1이 되는 최소 횟수를 알고 있다면??

(9가 1이 되는 최소 횟수) + 1 (10에서 1을 빼 9로 갈 때 횟수)을 해주면 쉽게 경우의 수를 찾을 수 있을 것이다.

10은 또 2로 나누어질 수 있기 때문에 2로 나누어서 시작하는 경우의 수도 알아보자. 10을 2로 나누면 5가 된다.

 

이때 5가 1이 되는 최소 횟수를 알고 있다면??

위와 마찬가지로 (5가 1이 되는 최소 횟수) + 1 (10을 2로 나눠 5로 만든 횟수)이 또 다른 경우의 수가 생긴다.

 

range(10, 2, -1)처럼 역으로 진행하는 방법을 처음에 생각해보았는데 아래와 같은 점화식을 사용해 순차적으로 쌓인 count를 통해 최종적으로 n의 최소값을 구하는 것이 핵심이라는 것을 알았다.

dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1

풀이

import sys

N = int(sys.stdin.readline())
answer = [0] * (N + 2)    # answer에 계산된 값을 저장해둔다.
# --> 0과 1이 입력될우 [0, 0]이 출력되어야 하므로 +1을 통해 자리를 만듬

# range는(시작, 끝-1)까지 돌아가므로 10까지 돌아가게 하기 위해 +1을 해야함
for i in range(N+1, 2, -1): # 0과 1은 count가 0이므로 제외하고 시작하기 위해 2부터 시작함
    # if문만을 이용해야 세 연산을 다 거칠 수 있다.
    # answer[i] = count숫자(즉 계산내역, -1 or % 2 or % 3)가 들어감
    answer[i] = answer[i - 1] + 1 # 밑에 두가지의 if문에 걸리지 않는다면 (ex : 5, 7, 11) 
    # --> answer[i-1] = 그전에 계산했던 count수 이므로 answer[i-1] + 1을 통해 -1이 계산되었다는것을 count해준뒤 다시 계산 
    # 2나 3으로 나누어질때 answer[i-1]과 비교하여 최소값을 answer[i]에 넣어줌
    if i % 3 == 0:
        answer[i] = min(answer[i], answer[i // 3] + 1)    # 1을 더하는 것은 answer는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다.
        # answer[i]에 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
    if i % 2 == 0:
        answer[i] = min(answer[i], answer[i // 2] + 1)
print(answer[N])