[백준] 15989번: 1, 2, 3 더하기 4

문제

백준 - 15989번: 1, 2, 3 더하기 4

분석

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.
수의 순서만 다른 것은 같은 것으로 친다.

수의 순서만 다른 것은 가짓수에 들어가지 않는다. 이 말은 고려하는 수들이 오름차순이거나 내림차순이면 순서만 다른 것을 가짓수에 뺄 수 있다.
이 풀이에서는 마지막으로 고른 숫자보다 크거나 같은 숫자만 고를 수 있게 했다.

정리하자면 i는 수들의 합, j는 마지막에 고른 숫자, 그리고 dp에 넣는 값은 가짓수이다.

i를 3까지 진행했을 때 경우가 몇가지 안되기에 손으로 풀어보면, 다음과 같다.
i==1 -> 1, i==2 -> 11, 2, i==3 -> 111, 12, 3

i＼j	1	2	3
1	1
2	1	1
3	1	1	1

이렇게 dp를 초기화하고, i를 4부터 진행한다.
현재 i에서 마지막에 j를 선택하기 위해 dp[i-j]를 고려한다. 그 중 ( jj ) 가 j보다 작거나 같을 때만 해당 dp값을 dp[i][j]에 더해준다.

원하는 n의 가짓수를 구하려면 해당 dp줄을 모두 더해야되기 때문에 sum(dp[n])을 출력한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

T = int(input())
MAX = 10000
dp = [[0]*4 for _ in range(MAX+1)]
for i in range(1, 4):
    for j in range(1, i+1):
        dp[i][j] = 1

for i in range(4, MAX+1):
    for j in range(1, 4):
        for jj in range(1, 4):
            if j >= jj:
                dp[i][j] += dp[i-j][jj]

for _ in range(T):
    n = int(input())
    print(sum(dp[n]))

끝으로..

내가 생각한 풀이로 한 번에 풀려서 좋았다.
다른 사람들은 더 쉽게 푼 것 같긴 하지만 내 풀이도 논리상 맞기 때문에 문제가 없다.