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

1. Question

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

1.1 Input

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

1.2 Output

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

1.3 Example

입력	출력
3 4 7 10	7 44 274

2. Approach

저번 포스트와 같이 간단한 DP 문제.

피보나치 마냥 1, 2, 3 단계 전의 계산 결과를 더하면 되는데, 이는 간단한 규칙으로 파악할 수 있다. 다음은 주어진 숫자마다 나올 경우의 수이다.

1
1

2
11
2

3
111
12
21
3

4
1111
112
121
211
22
13
31

5
11111
2111
1211
1121
1112
221
212
122
311
131
113
32
23

이제 각 수열의 맨 뒷 숫자를 보자.

4를 예로들면, 4에서 1로 끝나는 수열들은 1111, 121, 211, 31인데 여기서 맨끝의 1을 지우면, 111, 12, 21, 3인데 이것은 정확하게 3의 수열과 같다. 4에서 2로 끝나는 112, 22이고 2를 지우면, 11, 2 이며 이것은 2의 수열과 같다.

이 규칙을 통해 mem[i] = mem[i-1] + mem[i-2] + mem[i-3] 인 것을 알 수 있다.

3. Submission

4. Code

mem = [0] * 12
mem[1] = 1
mem[2] = 2
mem[3] = 4

for i in range(4, 12):
    mem[i] = mem[i - 1] + mem[i - 2] + mem[i - 3]

T = int(input())
for _ in range(T):
    case = int(input())
    print(mem[case])