[백준] 12852번: 1로 만들기 2 타일링 파이썬

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

12852번: 1로 만들기 2

안녕하띠오.

DP는 많이 풀어보는게 좋다고 해서 계속 푼다

파이띵

 

풀이

 

일단 문제에서 과정까지 출력해야하니 값테이블 말고 경로계산용 테이블도 만들어야함띠.

그래서 값테이블 arr, 경로계산 용은 arr2

 

뭔가 코드가 깔끔하지 않은 기분...............................

죄송티비

 

저는 계산용 테이블에 1, 2, 3 일케 저장했는데

바로 i-1, i//2, i//3 저장하는게

마지막 경로 출력 할때 더 편한듯. 

import sys
n = int(sys.stdin.readline())
arr = [0]*1000001
arr2= [0]*1000001
for i in range(2, n+1):
    arr[i] = arr[i - 1] + 1
    arr2[i] = 1
    if i % 3 == 0:
        arr[i] = min(arr[i//3] + 1, arr[i])
        if(arr[i//3] + 1 == arr[i]):
          arr2[i] = 3
    if i % 2 == 0:
        arr[i] = min(arr[i//2] + 1, arr[i])
        if(arr[i//2] + 1 == arr[i]):
          arr2[i] = 2
print(arr[n])
print(n, end=" ")
while(1):
  if arr2[n] == 1:
    n -= 1
    print(n, end=" ")
  elif arr2[n] == 2:
    n //= 2
    print(n, end=" ")
  elif arr2[n] == 3:
    n //= 3
    print(n, end=" ")
  else:
     break