[백준] 9095 | 1, 2, 3 더하기 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/9095

주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.

 

접근

방법을 구할 때, 수의 순서를 고려하는 것을 유념해야 한다. (1+2, 2+1을 별개로 본다.)

가짓수를 세다 보면 규칙을 발견할 수 있다.

f(n)이 n을 만들기 위한 방법의 수라고 할 때,

f(n) = f(n-3) + f(n-2) + f(n-1)이 된다.

이 문제에서는 n의 합을 구하기 위해 숫자 1, 2, 3만 사용한다.

n의 합은 ((n-3)의 합 +3) + ((n-2)의 합 +2) + ((n-1)의 합 +1)과 같다.

따라서 f(n-3) + f(n-2) + f(n-1) = f(n)이 된다.

 

코드

import sys
input = sys.stdin.readline

a = [0, 1, 2, 4]

for i in range(4, 12):
    a.append(a[i-3]+a[i-2]+a[i-1])

for _ in range(int(input())):
    print(a[int(input())])