코테 백준 1463 실버3

백준 1463

개인적으로 실버3이였지만 체감상 어려웠다. 처음에는 공배수인 6을 어떻게 할까, dp문제인걸 알지만 어떻게 점화식을 세우지? 노가다로 해보면서 규칙을 찾아야하나? 좀 어려움이 많았다. 학교에서 알고리즘 수업때 교수님께서도 dp는 쉽지 않다고했고 많은 연습을 해야한다고 말씀하셨다.

일단 기본 베이스는 차근차근 나아가는거다. 그래서 그다음 단계가 기존 방식의 다음단계와 특수한 다음단계중 최솟값을 비교해 작은것을 그다음 단계로 설정해놓고 푸는것이다.

일단은 다음단계가 이전단계보다 1증가시키고 그때 인덱스가 2의 나머지이면 (2로 나누어 떨어진 몫)번째 인덱스+1과 비교하면된다. 3도 마찬가지다. 하지만 6일경우 2와3일때를 비교해주어야하므로 그래서 elif가 아닌 if를 써주는것이다.

import sys
input = sys.stdin.readline

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

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