BOJ 1463 1로 만들기

https://www.acmicpc.net/problem/1463
시간 0.5초, 메모리 128MB
input :

• N (1 <= N <= 10^6)

output :

• 연산을 하는 횟수의 최솟값을 출력.

조건 :

• 정수에 사용하는 연산.

1. X가 3으로 나누어 떨어지면, 3으로 나눔.
2. X가 2로 나누어 떨어지면, 2로 나눔.
3. 1을 뺌.

---

DP 없이 재귀만 써서 하면 시간 초과가 발생할까?

최대 입력 되는 숫자는 1,000,000 1로 빼기만 해도 1백만 밖에 안 걸림..

재귀 함수로 구현하려 했는데.. 3 경우 모두 계산 해 줘야 하는데도 리턴에 걸려서 함수 밖으로 나가는 경우 발생.

dp 리스트 전체를 다 계산 해 놓고 인덱스로 아이템을 가져오자.

정답 코드 :

import sys

n = int(sys.stdin.readline())
dp = [0] * (n + 1)

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

print(dp[n])

점화식 만들기 부터 하고.
리스트를 다 채울지. 필요한 부분만 위에서 부터 재귀로 부를지. 생각해보자