[코딩 테스트 연습(파이썬/Python)] 백준 1463번 _ 1로 만들기

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

1463번: 1로 만들기

[문제]

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

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

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

 

[입력]

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

[출력]

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

[아이디어]

1) 낮은 숫자부터 연산 횟수를 쌓아나가야 할 것 같다.

 

d = [0] * 10**(6)
for i in range(1, 10**(6)):
    if not (i+1)%6:
        d[i] = min(d[(i//3)]+1, d[(i//2)]+1, d[i-1]+1)
    elif not (i+1)%3:
        d[i] = min(d[(i//3)]+1, d[i-1]+1)
    elif not (i+1)%2:
        d[i] = min(d[(i//2)]+1, d[i-1]+1)
    else:
        d[i] = d[i-1]+1
print(d[int(input())-1])

오히려 거꾸로 생각해야 한다. 이전에 가지고 있던 작은 숫자로부터 가장 빠르게 이후의 숫자를 만드는 방법을 찾는다고 생각한다.

2 <- 2

3 <- 1 or 2

4 <- 2

5 <- 4

6 <- 2 or 3 or 5

7 <- 6

8 <- 4 or 7 

9 <- 8 or 3

10 <- 5 or 9

 

위와 같이 나열해보면, 해당 숫자를 만들 수 있는 이전 단계의 숫자 중 가장 횟수가 적게 드는 숫자를 택해야함을 알 수 있다. 따라서 2부터 차례로 횟수를 쌓아가며, 이전의 횟수가 가장 짧은 숫자를 만드는 횟수 + 1을 새롭게 반환해야 한다. 리스트에 모두 저장하더라도, 이전의 것으로부터 이후의 것을 할당하는 동적 프로그래밍,,