[BOJ] 16195 - 1,2,3 더하기 9

[백준] 16195 - 1,2,3 더하기 9

아이디어

어떠한 수 n으로 접근하기 위해서는 3가지 갈래가 있다는 규칙을 발견할 수 있다.

1. n-1에 1을 추가한 경우
2. n-2에 2를 추가한 경우
3. n-3에 3을 추가한 경우 따라서 dp식을 다음과 같이 세울 수 있다.

   dp[n]=dp[n-1]+dp[n-2]+dp[n-3]
   

주의할 점

dp[n][1]은 모든 경우에서 1이 되는 것이 아니다. 이 점을 헷갈려 초기화문장을 for문 내에 써주었다가 틀렸다.ㅠㅠ

소스코드

MOD = 1000000009
dp = [[0 for _ in range(1005)] for _ in range(1005)]
dp[1][1] = dp[2][1] = dp[3][1] = 1
for i in range(1, 1001):
    for j in range(2, 1001):
        if i - 1 > 0 and j <= i:
            dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD
        if i - 2 > 0 and j <= i - 1:
            dp[i][j] = (dp[i][j] + dp[i - 2][j - 1]) % MOD
        if i - 3 > 0 and j <= i - 2:
            dp[i][j] = (dp[i][j] + dp[i - 3][j - 1]) % MOD
for T in range(int(input())):
    (n, m) = map(int, input().split())
    ans = 0
    for i in range(1, m + 1):
        ans = (ans + dp[n][i]) % MOD
    print(ans)