https://www.acmicpc.net/problem/1463
백준 1463 '1로 만들기' 문제입니다.
제가 처음 푸는 DP 문제인데 DP를 이해하지 못하다가 이 문제에서 처음으로 이해한 것 같습니다.
n마다 3으로 나누기, 2로 나누기, 1빼기 각각의 케이스를 시도하고 가장 작은 값을 취해주는 식으로 구현하였습니다.
import sys
input = sys.stdin.readline
n = int(input())
dp = [-1] * (n+1)
minValue = 99999999
for i in range(1, n+1):
if i % 3 == 0:
a = dp[i//3] + 1
else:
a = 999999
if i % 2 == 0:
b = dp[i//2] + 1
else:
b = 999999
c = dp[i-1] + 1
dp[i] = min(a, b, c)
print(dp[n])
'백준 알고리즘' 카테고리의 다른 글
파이썬) 백준 알고리즘 | 2792번 : 보석 상자 (0) | 2022.03.08 |
---|---|
파이썬) 백준 알고리즘 | 15666번 : N과 M (12) (0) | 2022.03.08 |
파이썬) 백준 알고리즘 | 15665번 : N과 M (11) (0) | 2022.03.04 |
파이썬) 백준 알고리즘 | 15664번 : N과 M (10) (0) | 2022.03.03 |
파이썬) 백준 알고리즘 | 15663번 : N과 M (9) (0) | 2022.03.03 |
댓글