[백준/Python] 9095번: 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

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

입력

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

출력

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

## n을 만들 수 있는 경우의 수 = n-1을 만들 수 있는 경우의 수 + n-2를 만들 수 있는 경우의 수 + n-3을 만들 수 있는 경우의 수
## 이 때, 인덱스가 1, 2, 3인 경우에는 각각 1, 2, 3도 들어가야 계산이 맞음.

t = int(input())

def in_range(q):
    global n
    return 0 <= q <= n

def update(q):
    global n
    for i in range(q - 3, q):
        if in_range(i):
            s[q] += s[i]

for _ in range(t):
    n = int(input())
    s = [0] * (n + 1)
    s[0] = 1 # 1, 2, 3에는 본인도 경우의 수로 들어가야 하므로, s[0]에 본인을 의미하는 1을 부여

    for i in range(n + 1):
        update(i)

    print(s[n])

풀이

n을 만들 수 있는 경우의 수 = n-1을 만들 수 있는 경우의 수 + n-2를 만들 수 있는 경우의 수 + n-3을 만들 수 있는 경우의 수 이다. 특정 정수를 1, 2, 3의 합으로 나타내어야 하기 때문이다.

n - 1을 만드는 경우에 1을 더하는 경우의 수, n - 2를 만드는 경우에 2를 더하는 경우의 수, n - 3을 만드는 경우에 3을 더하는 경우의 수들의 합이 n을 만들 수 있는 경우의 수이다.

이 때, 1, 2, 3의 경우에는 본인도 포함 시켜야한다. 그래야 그 이후의 계산에서 놓치는 경우의 수가 없이 모두 셀 수 있게 된다.

예를 들어 3의 경우, 1+1+1, 2+1, 1+2, 3으로 총  네  개의 경우의 수가 존재한다고 볼 수 있다.