BOJ(1,2,3 더하기(5))

작성일 | In

15990 1,2,3더하기(5)

  • 모르겠어서 다른 분들의 풀이를 찾아봤다.

  • 1,2,3 더하기(4)와 연관지어 생각해보자.

  • 1,2,3 더하기(4)는 수의 순서만 다른 것은 같은 것으로 친다고 하였다.

  • 이를 위해 ,먼저 1로 되는 수를 다 만들고, 2로 되는 수를 다 만들고, 3으로 되느 수를 만들었다.

  • 이번에는 중복할 수 없으니까.
  • 정수 n이 있을 때, 제일 마지막에 오는 수가 1이라면, -> 그 앞에 올 수 있는 수는 2나 3이다
  • 제일 마지막에 오는 수가 2이다. -> 그 앞에 올 수 있는 수는 1이나 3이다
  • 제일 마지막에 오는 수가 3이다 -> 그 앞에 올 수 있는 수는 1이나 2이다.

이를 점화식으로 표현하면 다음과 같다

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

코드

import sys
input = sys.stdin.readline
mod = 1000000009
d = [[0]*4 for i in range(100001)]
for i in range(1, 100001):
    if i - 1 >= 0:
        d[i][1] = d[i-1][2] + d[i-1][3]
        if i == 1:
            d[i][1] = 1
    if i - 2 >= 0:
        d[i][2] = d[i-2][1] + d[i-2][3]
        if i == 2:
            d[i][2] = 1
    if i - 3 >= 0:
        d[i][3] = d[i-3][1] + d[i-3][2]
        if i == 3:
            d[i][3] = 1
    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod

for _ in range(int(input())):
    n = int(input())
    print((d[n][1]+d[n][2]+d[n][3]) % mod)

참고자료 codeplus 참고블로그

0%