[백준, 파이썬, 16195번] 1, 2, 3 더하기 9

풀이

 

• 초기엔 재귀 함수를 사용해서 계속해서 값을 찾도록 했었지만 시간초과
• 이후 DP라고 해서 규칙을 찾고 난 다음 힌트를 얻게 됨.
• 우선 해당 수의 값은 1,2,3 번 이전의 수가 만들 수 있는 값의 합과 같다는 힌트를 얻음
• 그런데 여기서 또 해당 문제는 원하는 자릿수를 주기에 더 골치가 아팠다.
• 그래서 최대로 배열을 만든 다음 계속해서 값을 만들어준 다음 문제를 해결 

정답 코드

def startSetting():

    li[1][1] = 1

   

    li[2][1] = 1

    li[2][2] = 1

   

    li[3][1] = 1

    li[3][2] = 2

    li[3][3] = 1

import sys

input = sys.stdin.readline

val = 1000000009

li = [[0]*1001 for _ in range(1001)]

startSetting()

for i in range(4,1001):

    for j in range(1,i+1): li[i][j] = (li[i-1][j-1]+li[i-2][j-1]+li[i-3][j-1])%val

for _ in range(int(input())):

    n,m = map(int,input().split())

    print(sum(li[n][:m+1])%val)

 

시간 초과 코드

def find(num,cnt):

    global result

    if cnt == 0 or num == 0:

        if num == 0: result = (result+1)%1000000009

        return

    for i in range(1,4):

        if 0 > num-i or 0 > cnt-1: break

        find(num-i,cnt-1)

import sys

input = sys.stdin.readline

for _ in range(int(input())):

    result = 0

    n,m = map(int,input().split())

    find(n,m)

    print(result)