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

작성일 | In

1,2,3 더하기 3

  • 4를 1,2,3의 합으로 나타내는 방법은 총 7가지

  • 합을 나타낼 때는 수를 1개 이상 사용해야 함

  • 1,2,3 더하기와 차이점은 뭘까?
  • [1,2,3]은 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제였다.
  • 문제는 동일한데, 이번 문제는 입력의 정수 n의 범위가 1,000,000보다 작거나 같다고 한다.
d = [0, 1, 2, 4]
for i in range(4, 1000001):
    d.append((d[i-1]+d[i-2]+d[i-3]) % 1000000009)
for _ in range(int(input())):
    print(d[int(input())])

참고자료 codeplus 참고블로그

0%