https://www.acmicpc.net/problem/12852
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
'PS > DP' 카테고리의 다른 글
[백준] 11727번: 2×n 타일링 2 타일링 파이썬 (1) | 2024.03.04 |
---|---|
[백준] 11726번: 2×n 타일링 타일링 파이썬 (0) | 2024.03.04 |
[백준] 1149번: RGB거리 파이썬 (0) | 2024.03.04 |