[백준] 1463번-(Python 파이썬) - Dp

문제링크 : https://www.acmicpc.net/problem/1463

이번 문제는 처음 보자마자 while문을 이용하여 구현을 했다.
그리디 문제를 풀때처럼 처음에 3이나 2로 나눠질 때까지 -1로 빼는 식으로 계산을 했더니
수많은 반례들에 의해 난관에 부딪혔었다.
즉, 출제자의 의도는 단순 조건문으로의 풀이가 아닌, 다이나믹 프로그래밍이었다.

dp에 값을 저장해 n이라는 수가 3으로 나눴을 때의 그 수의 연산 수와
2로 나눴을 때의 그 수의 연산 수, 1로 뺏을때의 그 수의 연산 수 중 최소값을 출력하면 되는거였다.
그 생각을 가지고 재귀함수와 dp로 식을 만들었더니...결국 시간 초과가 나서
문제 해결 방법은 알지만 더 이상 시간을 쓰기 싫어 다른 분의 코드를 참고하여 다시 풀었다.

import sys
read = sys.stdin.readline

n = int(read())

dp = {
  0 : 0,
  1 : 0,
}

for i in range(2, n + 1):
  dp[i] = dp[i - 1] + 1

  if i % 2 == 0 and dp[i] > dp[i // 2] + 1:
    dp[i] = dp[i // 2] + 1

  if i % 3 == 0 and dp[i] > dp[i // 3] + 1:
    dp[i] = dp[i // 3] + 1

print(dp[n])

확실히 DP문제는 역시.. 메모이제이션이 힘든것보단 규칙을 찾는게 오래걸리는 것 같다.