[백준] 1463 1로만들기 - 파이썬

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

1463번: 1로 만들기

 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

N은 최대 1,000,000 까지 이고 파이썬은 1.5초까지 시간초과 나지 않습니다. 그러므로 O(N) 시간내에 해결해야합니다.

N의 개수만큼 dp 리스트를 만들고 0으로 초기화시킵니다.

1일때는 0, 2일때는 1, 3일때는 1입니다.

 

N이 4일때 부터는 앞에서 계산한 횟수(dp 배열 값)을 이용하면 한 번 만에 구할 수 있습니다.

왜냐하면 N을 계산하는 당시에는 N-1까지는 반드시 계산되어있다는 것이 자명합니다.

 

3번 조건 - N은 반드시 1을 뺄 수 있습니다. N-1은 반드시 nums 배열에 추가합니다.

1번 조건 - N을 3으로 나눌 수 있는 경우 N//3을 nums 배열에 추가합니다.

2번 조건 - N을 2로 나눌 수 있는 경우 N//2를 nums 배열에 추가합니다.

 

nums에 들어있는 숫자 중 dp[num]이 가장 작은 값을 찾으면 최솟값을 구할 수 있고

현재 단계를 거치기 때문에 1을 반드시 1을 더해주면 답을 찾을 수 있습니다.

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * 1000001
dp[1] = 0
dp[2] = 1
dp[3] = 1


for i in range(4, 1000001):
    nums = []
    nums.append(i-1)
    if i % 3 == 0:
        nums.append(i//3)
    
    if i % 2 == 0:
        nums.append(i//2)
    
    vals = []
    for num in nums:
        vals.append(dp[num])
    
    dp[i] = min(vals) + 1


print(dp[N])