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

1. 문제 설명

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

 

2. 풀이 전 계획과 생각

• test_case → 테스트 케이스 수
• 정수 → N

 

• 구하고자 하는 바 : 각 N마다 N을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하자.
  ⇒ DAG 구조다. 계산 중복을 방지하기 위해, DP로 해결해보자.
• 작은 문제 : dp[i] ⇒ i를 1, 2, 3의 합으로 나타낼 수 있는 방법의 수
• 풀고자 하는 문제 : dp[N] ⇒ N을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수
• base_case : dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 4
• 점화식 : dp[N]
  ⇒ 전체 경우의 수 = 각 Partition의 경우의 수들의 합이다.
  마지막에 1 더하는 경우들 + 1
  마지막에 2 더하는 경우들 + 2
  마지막에 3 더하는 경우들 + 3
  →
  마지막에 1 더하는 경우들 (합이 i-1인 경우들) + 1
  마지막에 2 더하는 경우들 (합이 i-2인 경우들) + 2
  마지막에 3 더하는 경우들 (합이 i-3인 경우들) + 3
  ⇒
  dp[i]
  = ((i-1)을 만들고 1 더하는 경우의 수) + ((i-2)을 만들고 2 더하는 경우의 수) + ((i-3)을 만들고 3 더하는 경우의 수)
  = dp[i - 1] + dp[i - 2] + dp[i - 3]

 

3. 풀이

def get_methods_num(N):
    dp = [0] * (N + 1)
    dp[0] = 0
    if N >= 1:
        dp[1] = 1
    if N >= 2:
        dp[2] = 2
    if N >= 3:
        dp[3] = 4

    for i in range(4, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    return dp[N]

test_case = int(input())
for _ in range(test_case):
    N = int(input())
    print(get_methods_num(N))

 

4. 풀이 후 알게된 개념과 소감

• 점화식을 어떻게 구해야 될지 모를 때,묶어낸 부분의 정답을 dp 배열을 이용해서 빠르게 계산해보자.
• 먼저, dp[i] 계산에 필요한 탐색 경우를 공통점끼리 묶어내보자.