1463 - 1로 만들기

 

---

문제 (S3)

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

1463번: 1로 만들기

 

 

풀이

D[n]은 n을 1로 만드는 최소한의 연산 개수가 들어가있다.

가능한 연산은 3개로, 1을 빼거나 2로 나누거나 3으로 나누거나이다.
최소한의 연산을 수행하기 위해서 우리가 우선순위로 두어야할 연산은 

1. 3으로 나누기
2. 2로 나누기
3. 1로 빼기 

일 것이다. 왜냐면 큰 숫자로 나누어야 연산이 최소화가 될테니까 말이다.

그래서 문제를 풀 때 모든 숫자에 적용 가능한 1로 빼기를 먼저 수행해보고, 이후에 2로 나뉘어지는지 체크해보고, 3으로 나뉘어지는지 체크하는 순으로 검사 및 갱신하면 된다.

 

코드

import sys

n = int(input())

d = [sys.maxsize] * 1000001

d[1] = 0
d[2] = 1
d[3] = 1

for i in range(4, 1000001):
    d[i] = d[i-1]
    # 2로 나눌 수 있다면
    if i%2 == 0:
        d[i] = min(d[i], d[i//2])
    if i%3 == 0:
        d[i] = min(d[i], d[i//3])
    d[i] += 1

print(d[n])