084 1로 만들기

첫번째 코드

 

dp를 이용한 첫번째 문제로 코드를 작성하는 방법은 보고 싶어서 책을 참고했다.

개인적으로 책에는 top-down이 더 쉽다고 나와있는데,

이전에 bottom-up을 경험해서 그런가... 점화식을 구하는게 더 마음이 편해서 그런가

개인적으로 top-down이 더 복잡했다...

 

조건에 거꾸로 진행된다고 생각하면 되는 것 같다.

문제 푸는 사람에 따라 푸는 방법이 다양할 것 같은 알고리즘이다.

 

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])

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/1463.%E2%80%851%EB%A1%9C%E2%80%85%EB%A7%8C%EB%93%A4%EA%B8%B0

programmers/백준/Silver/1463. 1로 만들기 at main · ornni/programmers