[백준 9095] 1, 2, 3 더하기

문제

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

접근

수들의 규칙성을 찾으려고 하였다. 4는 7가지의 경우의 수가 있었는데

1은 1, 2는 2, 3은 4의 경우의 수가 있었고 각 경우의 수를 펼쳤을 때 중복되는 연산이 많았다.

따라서 현재 N의 경우의 수는 N-1, N-2, N-3일 때의 경우의 수와 같다는 것을 알게되었다.

 

구현

먼저 1, 2, 3일 때를 먼저 구해놓고 이후의 수들은 for문을 통해 idx-1 + idx-2 + idx-3일 때의 경우의 수를 더해나갔다.

규칙만 알면 구현하는데 어려움은 없을 것이다.

test_case = int(input())
for _ in range(test_case):
    N = int(input())
    dp = [0 for _ in range(11)]
    dp[0] = 1 # 1
    dp[1] = 2 # 2
    dp[2] = 4 # 3
    answer = 0
    if N <= 3:
        answer = dp[N-1]
    else:
        for idx in range(3, N):
            dp[idx] = dp[idx-1] + dp[idx-2] + dp[idx-3]
        answer = dp[N-1]

    print(answer)