Algorithm/BOJ
[python 파이썬] 백준 1463번 1로 만들기
징늬2
2021. 2. 2. 00:47
반응형
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
이 문제는 DP의 가장 대표적인? 예제 같다. 외우듯이 알아두자
# 1463번 1로 만들기
n = int(input())
dp = [0 for _ in range(n+1)]
for i in range(2,n+1):
dp[i]=dp[i-1]+1
if i%3 ==0 and dp[i//3]+1<dp[i]:
dp[i]=dp[i//3]+1
if i%2 ==0 and dp[i//2]+1<dp[i]:
dp[i]=dp[i//2]+1
print(dp[n])
반응형