[BOJ/Python] 1로 만들기 2 || 다이나믹 프로그래밍

백준 1로 만들기 2 파이썬 12858

12852번: 1로 만들기 2

❍ 문제

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

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

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

❍ 입력

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

❍ 출력

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

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

 

❏ 문제 풀이

dp[i] : i가 1이 되는 과정을 담았다.
i를 3으로 나눠야 하는 경우엔, dp[i] = [i] + dp[i // 3]이 된다.
다만, 1이 되는 연산의 횟수가 최솟값이 되어야 하므로 횟수의 길이를 비교해주어야 한다.
3으로 나눠지지만, 2로 나눠질 때나 1을 뺀 경우가 더 최솟값이 될 수 있기 때문에, 비교가 필요하다.
 

❍ CODE

import sys

input = sys.stdin.readline
n = int(input())
dp = [[i] for i in range(n + 1)]
dp[1] = [1]
for i in range(2, n + 1):
    if i % 3 == 0:
        dp[i] = [i] + dp[i // 3]

    if i % 2 == 0:
        if len(dp[i]) == 1 or len(dp[i]) > len(dp[i // 2]) + 1:
            dp[i] = [i] + dp[i // 2]

    if len(dp[i]) == 1 or len(dp[i]) > len(dp[i - 1]) + 1:
        dp[i] = [i] + dp[i - 1]

print(len(dp[n]) - 1)
print(*dp[n])

 

❍ CODE

import sys

input = sys.stdin.readline
n = int(input())
dp = [0] * (n + 1)
path = [[i] for i in range(n + 1)]

path[1] = [1]

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    path[i] = [i] + path[i - 1]

    if i % 3 == 0 and dp[i] > dp[i // 3] + 1:
        dp[i] = dp[i // 3] + 1
        path[i] = [i] + path[i // 3]
    if i % 2 == 0 and dp[i] > dp[i // 2] + 1:
        dp[i] = dp[i // 2] + 1
        path[i] = [i] + path[i // 2]

print(dp[n])
print(*path[n])

 

❏ 삽질 기록

❍ Issue #1

dp[i] += dp[i // 2] 이런식으로 +=를 사용해줬었는데, 이전에 변경된 값에 덧붙여지는 경우가 생기기 때문에, dp[i] = [i] + dp[i // 2]처럼 초기화해주는 방식으로 변경하였다.
 

❍ Issue #2

입력이 1부터 가능한데, 2부터 가능하다고 착각하여 dp[2]를 초기화해주게 되었다. 그러면 1이 들어오는 순간 리스트의 범위가 벗어나므로 런타임 에러가 발생한다. 이를 고쳐주었다.