백준(Python) 풀이/다이나믹 프로그래밍

백준(Python) 1463번 1로 만들기 풀이

개발윗미 2021. 10. 21. 11:38

Python으로 구현한 1463번 1로 만들기 문제 풀이입니다.

 

https://www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net


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

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

 

1. n이 3으로 나누어 떨어지면, 3으로 나눈다.

 

2. n이 2로 나누어 떨어지면, 2로 나눈다.

 

3. 1을 뺀다.

 

위 세가지의 방법을 모두 하나씩 진행하여 최솟값을 구해 dp 리스트에 담는 방식으로 진행한다.