[백준] 15989번 - 1, 2, 3 더하기 4 문제 풀이

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

문제

 

정수 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

 

1. 문제 분석

기존 1, 2, 3 더하기 문제와의 차이

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

 

보통의 1, 2, 3 더하기 문제(예: 백준 9095번)는 순서를 따집니다.

• 예: 1+2와 2+1을 다른 경우로 셈.
• 이때의 점화식: dp[n]=dp[n−1]+dp[n−2]+dp[n−3]

이 문제(15989)의 핵심

하지만 이 문제는 순서가 달라도 구성이 같으면 같은 경우로 생각합니다.

• 예: 1+2와 2+1은 같은 경우 (중복 제거 필요)

---

2. 동전 교환 알고리즘과 유사!!

순서 중복을 없애는 가장 확실한 방법은 수를 오름차순으로만 사용하도록 정하는 것입니다. 

1을 모두 사용한 뒤 2를 쓰고, 그 뒤에 3을 쓰는 방식으로만 합을 구성하면,  2+1 같은 순서 뒤집힘이 발생하지 않습니다.

-> 동전 교환 문제 

흐름

Step 1: 1만 사용하여 만드는 경우 모든 수는 1의 합으로 나타낼 수 있습니다. (1+1+…)

• 초기화: 모든 dp[i]=1 (혹은 dp[0]=1에서 시작하여 갱신)

Step 2: 2를 추가하여 만드는 경우 이미 1로만 구성된 경우의 수에, 이제 2를 섞어서 만들 수 있는 경우를 더합니다.

• 점화식: dp[i]=dp[i]+dp[i−2]
•  i−2를 만드는 모든 방법 뒤에 2를 하나 붙인다.

Step 3: 3을 추가하여 만드는 경우 1과 2로 구성된 경우의 수에, 마지막으로 3을 섞는 경우를 더합니다.

• 점화식: dp[i]=dp[i]+dp[i−3]
•  i−3을 만드는 모든 방법 뒤에 3을 하나 붙인다.

 for 문의 순서가 중요. 동전을 바깥쪽 루프에 두고, 금액을 안쪽 루프에 두어야 중복 없는 조합이 계산됨

 

---

3. 코드 

테스트 케이스가 여러 개지만, n의 최댓값이 10,000으로 작으므로 DP 테이블을 미리 한 번만 채워두고 결과를 조회하는 것이 효율적

import sys
input = sys.stdin.readline

# 1. 입력 받기
T = int(input())
nums = [int(input()) for _ in range(T)]

# 2. DP 테이블 초기화
# 문제 조건에 따라 n은 최대 10,000
max_n = 10000 
dp = [0] * (max_n + 1)

# 초기값: 0을 만드는 방법은 아무것도 선택하지 않는 1가지
dp[0] = 1 

# 3. DP 
# 숫자를 하나씩 고정하고 dp 테이블 전체를 갱신한다.
# 이렇게 하면 (1, 2) 조합 다음 (1, 3)이 올 수 있어도, 
# (2, 1) 처럼 순서가 바뀌는 경우는 발생하지 않는다.

for num in [1, 2, 3]:  # 사용할 수 있는 숫자
    for i in range(num, max_n + 1):
        dp[i] += dp[i - num]

# 4. 결과 출력
for n in nums:
    print(dp[n])

---

4. 정리

이 문제의 교훈은 DP에서 루프의 순서가 의미를 바꾼다는 것입니다.

1. 순서가 중요할 때 -순열: target을 바깥 루프, coins를 안쪽 루프로.
2. 순서가 중요하지 않을 때 -조합: coins를 바깥 루프, target을 안쪽 루프로.

이 문제는 순서가 중요하지 않으므로 2번 방식을 사용하여 해결했습니다.