https://www.acmicpc.net/problem/12852
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]))
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 9466번 텀 프로젝트 (1) | 2023.01.03 |
---|---|
[백준/파이썬] 2252번 줄 세우기 (1) | 2022.12.31 |
[백준/python] 15684번 사다리 조작 (0) | 2022.12.26 |
[백준/파이썬] 18185번 라면 사기(small) (0) | 2022.12.22 |
[백준/C++] 1644번 소수의 연속합 (0) | 2022.12.21 |