다이나믹 프로그래밍 한접시
[백준] 1로 만들기 2 [Python]
NaZZU
2024. 4. 29. 14:57
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
if __name__ == "__main__":
num = int(input())
arr = []
dp = [0, 0]
for i in range(2, num+1):
if (i % 6 == 0):
dp.append(min(dp[int(i / 3)], dp[int(i / 2)]) + 1)
elif (i % 3 == 0):
dp.append(min(dp[int(i / 3)], dp[i - 1]) + 1)
elif (i % 2 == 0):
dp.append(min(dp[int(i / 2)], dp[i - 1]) + 1)
else:
dp.append(dp[i - 1] + 1)
temp = num
while (temp >= 1):
if (temp % 6 == 0):
if (dp[int(temp / 3)] < dp[int(temp / 2)]):
arr.append(temp)
temp = int(temp / 3)
else:
arr.append(temp)
temp = int(temp / 2)
elif (temp % 3 == 0):
if (dp[int(temp / 3)] < dp[int(temp - 1)]):
arr.append(temp)
temp = int(temp / 3)
else:
arr.append(temp)
temp -= 1
elif (temp % 2 == 0):
if (dp[int(temp / 2)] < dp[int(temp - 1)]):
arr.append(temp)
temp = int(temp / 2)
else:
arr.append(temp)
temp -= 1
else:
arr.append(temp)
temp -= 1
print(dp[num])
for _ in arr:
print(_, end=' ')
|
cs |
