[백준/파이썬] 12852번 1로 만들기 2

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

12852번: 1로 만들기 2

DP문제이다. 여느 DP문제가 그렇듯, 탑다운이 아니라 바텀업으로 풀어야한다.

 

이 문제의 점화식은 아래 3가지 조건을 만족해야한다. 점화식을 f(x)라 하자. 

1. f(x) = f(x-1) + 1                         --> 1을 더해서 만드는 경우

2. if x % 3 == 0, f(x) = f(x/3) + 1 --> x가 3으로 나눠질 때

3. if x % 2 == 0, f(x) = f(x/2) + 1 --> x가 2로 나눠질 때

 

※ 여기서 더하기 1은 경우의 수가 하나 증가함을 의미한다!!

 

예를 들어 설명해보자면, 우리가 5라는 숫자를 만들기 위해선 4라는 숫자를 만들고 1을 더해주면 된다. (조건1 이용)

즉, f(5) = f(4) + 1이다.

 

그럼 f(4)는 어떻게 만드냐? 2라는 숫자에 곱하기 2를 하거나 3이라는 숫자에 더하기 1을 해주면 된다. (조건1 또는 조건2 이용)

f(4) = f(4/2) + 1 또는 f(4) = f(3) + 1이 될 것이다.

 

f(2) = f(1) + 1이 될 것이고 f(1)은 0이다. (1을 만드는 경우는 그냥 1이라는 숫자 자체로 만족하기 때문) (조건1)

f(3) = f(3/3) + 1 이 될 것이고 마찬가지로 f(1)은 0 이므로 f(3)은 1이다. (조건3)

 

f(10)은 f(9) + 1과 f(5) + 1을 비교해서 최솟값이 되는 경우를 선택할 것이다. 정답의 경우는 9이므로 9를 선택했다고 하자

f(9)는 f(8) + 1과 f(3) + 1을 비교할 것이고, 이런식으로 쭉쭉 비교해서 수를 1로 만들것이다.

 

정리하자면, f(1) = 0, f(2) = 1, f(3) = 1, f(4) = 2, f(5) = 3이다.

 

일단 조건1을 이용해 +1로 채워준뒤, 2나 3으로 나눠주면 그 때 조건2,3을 이용해 값을 찾고 먼저 채운 값과 나중에 발견한 값 중 최솟값을 담아주면 된다.

이때 사용되는 숫자들은 그냥 리스트에 담아주고 역순으로 출력해주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0, []] for _ in range(n + 1)]
dp[1][0] = 0
dp[1][1] = [1]

for i in range(2, n + 1):
	# 조건 1 이용해서 일단 +1
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    # 조건 2,3, 이용해서 2나 3으로 나눠질 때 최솟값 비교
    if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 3][0] + 1
        dp[i][1] = dp[i // 3][1] + [i]
    if i % 2 == 0 and dp[i // 2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 2][0] + 1
        dp[i][1] = dp[i // 2][1] + [i]

print(dp[n][0])
print(*reversed(dp[n][1]))