DP 문제 내맘대로 풀기(백준 15989 python)

문제 링크

(DP문제긴 하지만 풀이는 수학!)
사실 이 문제를 처음 봤을 때 이게 DP인지 모르고 접근했다.
(풀고, 유형까지 안 지금도 나름 정석이랄 수 있는 DP로 푸는 방법은 모르겠다.)

처음으로 문제에 대한 관찰을 해보자..
아래 수는 문제의 조건을 따졌을 때 차례대로 0부터 6까지 만들 수 있는 모든 방법의 수이다.

X

1

1+1
2

1+1+1
2+1
3

1+1+1+1
2+1+1
2+2
3+1

1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
3+2

1*6
2+1*4
2*2+1*2
2*3
3+1*3
3+2+1*2
3+3

1. 처음 방법을 생각했을 때는 피보나치 수열의 확장판인가? 생각했다가 순서만 바뀌는 경우 같은 방법으로 취급한다는 말에 아니겠거니.. 하고 reject.
2. 다음으로 3의 갯수에 따라 카운트를 해볼까? 하고 수를 계산해보게 되었다. 예를 들어 3과 6을 생각해보자.
   3에서 3이 없이 조합할 수 있는 경우는1+1+1, 2+1이고, 6에서 3을 하나 가지고 조합하는 경우는 3을 제외하면 동일하게 1+1+1, 2+1이다. 비슷하게 3에서 3을 한개 가지고 조합하는 경우는 X, 6에서 3을 2개 가지고 조합하는 경우는 X. 이 원리를 이용해서
   숫자가 하나 주어졌을 때 그 아래 수가 1,2로 조합되는 가짓수를 찾아보았다.
   그 결과는
   [1,1,2,2,3,3,4,4,5,5,6]
# 0을 포함한 10 이하의 수가 1,2로 조합되는 경우의 수
   그리고 그 함수를 짜보면..

two_num = []
n = 10
for i in range(n+1):
    two_num.append(int(i)//2+1)

print(two_num) # [1,1,2,2,3,3,4,4,5,5,6]

그리고 이걸 통해 주어진 예시였던 10을 count해보았을 때
two_num[1]+two_num[4]+two_num[7]+two_num[10] == 1+3+4+6 == 14

이걸 이용해서 로직을 구현해보았다.

from sys import stdin

case = int(stdin.readline().strip())

two_num = []
three_num = 0
three_div = 0
for _ in range(case):
    num = int(stdin.readline().strip())
    three_num = num//3 + 1
    three_div = num%3
    if len(two_num)<num+1:
        for i in range(len(two_num),num+1):
            two_num.append(i//2+1)

    result = 0
    for i in range(three_div,num+1,3):
        result += two_num[i]
    
    print(result)

이경우 two_num은 초기화시킬 필요가 없어보여서, 그냥 기존에 나왔던 수보다 더 큰수가 num에 들어가면 길이를 늘리는 식으로 코드를 구현하게 되었다.

결과는

아마 DP를 써서 풀었다면 72ms에서 88ms 정도 걸리는 것 같은데 나쁘지 않은 결과였다.
(생각해보니 이 방법도 DP인가? 하는 의문이 든다.)