[백준] 9095 : 1, 2, 3 더하기 (파이썬 / Python)

1, 2, 3 더하기

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

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의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 

3
4
7
10

예제 출력 1 

7
44
274

---

코드

T = int(input())

for i in range(T):
    n = int(input())
    d = [0] * (n+1)
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    elif n == 3:
        print(4)
    else:
        d[1] = 1
        d[2] = 2
        d[3] = 4
        for j in range(4, n+1):
            d[j] = d[j-1] + d[j-2] + d[j-3]
        else:
            print(d[n])

풀이

우선 해당 문제는 동적계획법의 bottom-up 방식으로 풀 수 있다. 동적계획법으로 풀이가 가능한 이유는 작은 문제를 이 결과값을 활용하여 큰 문제를 풀 수 있기 때문이다. 또한, 초기값을 쉽게 알 수 있으므로 bottom-up 방식으로 풀면 된다.

이 문제의 포인트는 정수 n이 주어졌을 때 이를 분할하여 [1, 2, 3]의 합으로 나타내는 방법의 수를 구하는 것이다. 즉, 3보다 더 큰 숫자로 분할이 된다고 하더라도 이는 경우의 수에 카운팅하면 안 된다는 의미이다.

n = 1인 경우는 1,

n = 2인 경우는 2, 1+1

n = 3인 경우는 3, 2+1, 1+2, 1+1+1로 쉽게 구할 수 있다.

d를 합으로 나타내는 방법의 수를 저장하는 배열이라고 할 때, d[1] = 1, d[2] = 2, d[3] = 4로 나타낼 수 있다.

문제는 이를 이용하여 n > 3일 때의 규칙을 찾아 이를 점화식으로 표현하는 것이다. 

n = 4일 때를 생각하여 보자. 1 + 3, 2 + 2, 3 + 1으로 나타낸 것을 살펴보자. 부호를 기준으로 앞에 있는 수는 가능한 분할의 기준 수이며, 뒤에 있는 수는 n = 3, n = 2, n = 1일 때의 분할을 의미한다. 

n = 5일 때를 생각하여 보자. 1 + 4, 2 + 3, 3 + 2으로 나타낸 것을 살펴보자. 부호를 기준으로 앞에 있는 수는 가능한 분할의 기준 수이며, 뒤에 있는 수는 n = 4, n = 3, n = 2일 때의 분할을 의미한다. 

즉, n > 3일 때의 점화식은 d[n] = d[n-1] + d[n-2] + d[n-3]으로 나타낼 수 있다.