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

제한

시간 제한	메모리 제한
1sec (추가 시간 없음)	512MB

---

풀이

정수 $n$을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. 단, 합을 이루는 수의 순서만 다른 것은 같은 것으로 간주하므로, 중복을 피하기 위해 선택하는 수의 순서를 오름차순으로 고정하는 전략이 필요하다. 이를 위해 다이나믹 프로그래밍(Dynamic Programming)을 활용하여 각 정수를 만드는 조합을 체계적으로 계산한다.

핵심 아이디어는 정수 $i$를 만들 때 마지막으로 더해진 수가 무엇인지에 따라 상태를 나누는 것이다. $DP[i][j]$를 “정수 $i$를 만드는 방법 중, 사용된 수 중 가장 큰 수가 $j$인 경우의 수”라고 정의하면 다음과 같은 점화식을 세울 수 있다:

\[DP[i][1] = DP[i-1][1]\] \[DP[i][2] = DP[i-2][1] + DP[i-2][2]\] \[DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3]\]

각 식의 의미는 다음과 같다:

1. $DP[i][1]$: 오직 1만을 사용하여 $i$를 만드는 방법이다. 항상 1가지이다.
2. $DP[i][2]$: 마지막에 2를 더해 $i$를 만드는 경우다. 중복을 피하기 위해 이전에 사용된 수는 1 또는 2여야 한다.
3. $DP[i][3]$: 마지막에 3을 더해 $i$를 만드는 경우다. 이전에 사용된 수는 1, 2, 또는 3이어야 오름차순이 유지된다.

이 문제에서 $n$은 최대 $10\,000$이므로, $O(n)$의 시간 복잡도로 미리 모든 값을 계산해 두면 각 테스트 케이스에 대해 즉각적인 응답이 가능하다. 최종적으로 정수 $n$에 대한 답은 $DP[n][1] + DP[n][2] + DP[n][3]$이 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍