[BOJ/Step15] 1463 : 1로 만들기 (Python)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

처음엔 입력값이 너무 커서 순서대로 하면 무조건 시간초과 날 줄 알고 겁먹었다

근데 다른 방법이 떠오르지 않아서 일단 이전 dp문제들처럼 풀어봄

 

리스트에 각 숫자가 입력되었을 때의 최소 연산 수를 저장할 것!

 

그 숫자는 1을 빼거나, 3으로 나누거나, 2로 나눠야 한다.

그런데 연산 횟수의 최솟값을 구해야 하니까

1을 빼거나, 3으로 나누거나, 2로 나눴을 때 중 가장 작은 연산 횟수를 가진 연산을 행하면 된다.

f(n) = min(f(n-1), f(n//3), f(n//2)) + 1

 

1. 리스트 num에 미리 n개의 0을 넣어두고 num[2], num[3]에는 1을 저장

2. 4부터 n까지 반복문을 통해 값을 넣을 것

  2-1. num[i]에 num[i-1] + 1을 저장 ( i가 2나 3으로 나누어지지 않는 경우도 있기 때문 )

  2-2. i가 3으로 나누어지면 num[i]와 num[i//3]+1 을 비교하여 더 작은 수를 저장

         ( 이미 num[i]에는 num[i-1] + 1이 저장되어 있기 때문 )

  2-3.  i가 2로 나누어지면 num[i]와 num[i//2]+1 을 비교하여 더 작은 수를 저장

         ( 이미 num[i]에는 num[i-1] + 1 또는 num[i//3]+1 이 저장되어 있기 때문 )

3. num[n]을 출력

# 1463.py

n = int(input())

num = [0, 0, 1, 1] + [0 for _ in range(n-3)]

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

print(num[n])