BAEKJOON : 2225, 15988

No. 2225

1. Problem

2. Others' Solutions

• dp[n][k] 리스트를 생성하여 dp 구현
• 첫 번째 방법
  

import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
dp = [[0]*(k+1) for _ in range(n+1)]
const = 1000000000

for i in range(n+1):
    dp[i][1] = 1

for j in range(2,k+1):
    for i in range(0,n+1):
        for q in range(i+1):
            dp[i][j] += (dp[q][j-1] % const)

print(dp[n][k] % const)

• 두 번째 방법 (규칙 찾아내기)
  

dp[n][k] = (dp[n-1][k] + dp[n][k-1]) % const

3. Learned

• 2차원 배열을 이용해서 dp 구현시 1차원과 2차원에 어떤 요소를 저장할 것인지 판단하자
• 점화식을 최대한으로 생각해보자

---

No. 15988

1. Problem

2. My Solution

• 이전의 1,2,3 더하기 는 n 이 11 까지지만 이번에는 1000000
• 시간초과를 방지하기 위해 먼저 dp 를 이용해서 값을 저장한뒤 테스트케이스에선 답만 print

import sys

test_n = int(sys.stdin.readline().rstrip())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4,1000001):
    dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009

for _ in range(test_n):
    n = int(sys.stdin.readline().rstrip())
    print(dp[n] % 1000000009)