1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
아이디어:
조건:
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
dp[i] = min(dp[i-1], dp[i//3], dp[i//2]) #i가 3,2로 나누어 떨어지는 경우..
dp[1]=0, dp[2]=dp[3]=1
n까지 bottom-up 방식으로 반복문을 이용하여 구현하였다.
import sys
n = int(sys.stdin.readline())
dp = [0]*(1000001)
dp[2]=1
dp[3]=1
for i in range(4,n+1):
a = i%3
b = i%2
if (a==0):
if (b==0):
dp[i] = min(dp[i-1], dp[i//3], dp[i//2])+1
else:
dp[i] = min(dp[i-1], dp[i//3])+1
else:
if (b==0):
dp[i] = min(dp[i-1], dp[i//2])+1
else:
dp[i] = dp[i-1]+1
print(dp[n])
'알고리즘💻 > DP' 카테고리의 다른 글
BOJ 14494번: 다이나믹이 뭐예요? (0) | 2021.01.24 |
---|---|
BOJ 20500번: Ezreal 여눈부터 가네 ㅈㅈ (0) | 2021.01.24 |
BOJ 1757번: 달려달려 (0) | 2021.01.24 |
BOJ 15988번: 1, 2, 3 더하기 3 (0) | 2021.01.24 |
BOJ 2748번: 피보나치 수 2 (0) | 2021.01.24 |