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

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

 

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

1463번: 1로 만들기

---

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 리스트에 담는 방식으로 진행한다.