[ BAEKJOON ] 1, 2, 3 더하기 4 / 15989 / Python

 

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

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

입력

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

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

4
8
14

---

나의 풀이

문제 설명 및 해결 방법

이 문제는 DP(Dynamic Programming)로 해결할 수 있습니다.

다만, 점화식을 도출하는 과정이 어려웠던 관계로 인터넷을 참고하여 문제를 해결하게 되었습니다.

 

문제 조건

1, 2, 3만을 사용하여 주어진 숫자를 만드는 방법의 수를 구합니다.

여기서 중요한 점은 같은 숫자 조합이라도 순서가 다르면 동일한 경우로 간주한다는 것입니다.

예를 들어, 1+1+2와 1+2+1은 같은 조합으로 봅니다. 따라서 조합의 숫자를 오름차순으로 나열해 문제를 해결합니다.

 

 

예제: 숫자 7을 만드는 경우

숫자 7을 1, 2, 3을 이용해 만드는 경우를 나열하면 다음과 같습니다.

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

이처럼, 마지막 숫자가 몇인지에 따라 조합의 제약이 달라집니다.

예를 들어:

• 마지막 숫자가 2라면, 앞의 숫자는 2 이하만 가능합니다. (3이 올 수 없음)
• 마지막 숫자가 1이라면, 모든 숫자가 1로만 이루어진 조합이 됩니다.

 

점화식 도출 과정

작은 숫자부터 점진적으로 경우의 수를 계산하는 바텀업 방식으로 해결합니다.

숫자 n을 만드는 경우의 수를 dp[n]이라 정의합니다.

여기서 dp[n][k]는 숫자 n을 만들 때 마지막 숫자가 k인 경우의 수를 나타냅니다.

 

기본 규칙

1. 숫자 n을 만드는 방법의 총 경우의 수는, dp[n][1], dp[n][2], dp[n][3]의 합입니다.
   즉, dp[n]=dp[n][1]+dp[n][2]+dp[n][3]
2. dp[n][k]는 다음과 같이 계산됩니다.
   • 마지막 숫자가 1인 경우: dp[n][1]=dp[n−1][1]
   • 마지막 숫자가 2인 경우: dp[n][2]=dp[n−2][1]+dp[n−2][2]
   • 마지막 숫자가 3인 경우: dp[n][3]=dp[n−3][1]+dp[n−3][2]+dp[n−3][3]

 

표로 보는 과정 예시

아래 표는 숫자를 1~7까지 만들기 위한 경우의 수를 계산한 과정을 나타냅니다.

숫자	마지막 숫자가 1인 경우	마지막 숫자가 2인 경우	마지막 숫자가 3인 경우	dp[n]
1	1	0	0	1
2	1	1	0	2
3	1	1	1	3
4	1	2	1	4
5	1	2	2	5
6	1	3	3	7
7	1	3	4	8

 

예시 풀이

숫자 7을 구하는 방법을 예로 들어보겠습니다.

1. 마지막 숫자가 1인 경우:숫자 6을 만들 때 마지막 숫자가 1인 경우에 1을 더하면 됩니다.
   따라서, dp[7][1]=dp[6][1]=1
2. 마지막 숫자가 2인 경우:숫자 5를 만들 때 마지막 숫자가 1 또는 2인 경우에 2를 더하면 됩니다.
   따라서, dp[7][2]=dp[5][1]+dp[5][2]=1+2=3
3. 마지막 숫자가 3인 경우:숫자 4를 만들 때 마지막 숫자가 1, 2, 3인 경우에 3을 더하면 됩니다.
   따라서, dp[7][3]=dp[4][1]+dp[4][2]+dp[4][3]=1+2+1=4
4. 숫자 7의 총 경우의 수: dp[7]=dp[7][1]+dp[7][2]+dp[7][3]=1+3+4=8

 

---

 

코드

위 점화식을 바탕으로 DP 배열을 채우면, 숫자 n을 만드는 모든 경우의 수를 효율적으로 구할 수 있습니다.

이를 코드로 구현하면 다음과 같습니다.

tc = int(input())
arr = list()
for _ in range(tc):
    arr.append(int(input()))

mx = max(arr)

# DP 만들기
dp = list()
for _ in range(mx):
    dp.append([0] * 3)

dp[0][0] = 1
dp[1][0] = 1
dp[1][1] = 1
dp[2][0] = 1
dp[2][1] = 1
dp[2][2] = 1

# 점화식에 의한 계산
if mx > 2:
    for i in range(3, mx):
        dp[i][2] = dp[i-3][2] + dp[i-3][1] + dp[i-3][0]
        dp[i][1] = dp[i-2][1] + dp[i-2][0]
        dp[i][0] = dp[i-1][0]

# 정답
for i in arr:
    print(dp[i-1][0] + dp[i-1][1] + dp[i-1][2])