https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
n = int(input())
arr = [0, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16]
for i in range(12, 100001):
# arr.append()
# a = arr[i]
arr.append(arr[i-6] + i)
for i in range(n):
num = int(input())
print(arr[num])
이 문제는 DP를 이용한 문제이다.
1부터 20까지 쭉 나열해보니 6보다 큰 경우, arr[i-6] + number가 성립되었다.
생각해보면 이토록 단순한 문제였는데 너무 어려운 문제들에게 둘러싸여 있어서 오히려 무척이나 해맸다.
어떻게 20까지 구했나보면 직접 dfs를 구현해서 20까지 출력을 해보았다.
# dfs 구현으로 20까지 출력
from copy import deepcopy
n = int(input())
cnt = 0
def dfs(target, num, history, arr):
if target == num:
history.sort()
if history in arr:
return
else:
global cnt
arr.append(history)
cnt += 1
return
if target < num:
return
for i in range(3):
a = deepcopy(history)
a.append(i+1)
dfs(target, num+i+1, a, arr)
# dfs(target)
i = 1
while i <= 40:
arr = []
cnt = 0
arr = []
dfs(i, 1, [1], arr)
dfs(i, 2, [2], arr)
dfs(i, 3, [3], arr)
print(i, ' = ', cnt)
i += 1