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

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

12852번: 1로 만들기 2

[문제]

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

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

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

 

[입력]

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

[출력]

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

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

[아이디어]

1) 2차원 dp를 활용해 1부터 n까지 업데이트 해나가면서, 연산(*3 / *2 / +1)을 하기 이전의 값이 무엇이었는지를 함께 기록하도록 했다.

2) 이후 n에 도달하면 다시 역으로 이전 값들을 추적해 출력한다.

 

n=int(input())
dp = [[0,0] for _ in range(n+1)]
for i in range(2,n+1):
    if i%6==0:
        tmp = min(dp[i//3][0], dp[i//2][0], dp[i-1][0])
        for x in [i//3,i//2,i-1]:
            if dp[x][0]==tmp:
                dp[i][1]=x
                break
        dp[i][0] = tmp +1
    elif i%3==0:
        dp[i][0] = min(dp[i//3][0], dp[i-1][0]) +1
        dp[i][1] = [i//3,i-1][dp[i//3][0]>dp[i-1][0]]
    elif i%2==0:
        dp[i][0] = min(dp[i//2][0], dp[i-1][0]) +1
        dp[i][1] = [i//2,i-1][dp[i//2][0]>dp[i-1][0]]
    else:
        dp[i][0] = dp[i-1][0]+1
        dp[i][1] = i-1
print(dp[n][0])
tmp = [n]
while n!=1:
    tmp.append(dp[n][1])
    n = dp[n][1]
print(*tmp)

for문 안의 수를 n까지 돌게 하면 통과인데, 최악의 경우인 10**6을 모두 계산하게 하면 시간초과가 난다.