[골드 5] 백준 15989 - 1, 2, 3 더하기 4 (파이썬)

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

풀이

• 정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라
• 같은 수라도 순서가 다른 것은 같은 경우로 취급한다.
• 예를 들어 3 = 1 + 2 와 2 + 1은 같은 경우로 처리된다.

DP 배열을 아래와 같이 정의한다.

D = [[0] * 10001 for _ in range(4)]

D[i][j]는 1부터 i까지의 숫자만 사용해서 j를 만드는 경우의 수를 의미한다.

• 예를 들어서 D[2][4]는 1, 2만 사용해서 4를 만드는 방법의 수를 나타낸다.

점화식은 아래와 같이 구성한다.

D[0][0] = 1
for i in range(1, 4):  # 1, 2, 3 사용
    for j in range(10001):
        D[i][j] = D[i - 1][j]  # i를 사용하지 않는 경우
 
        if j >= i:
            D[i][j] += D[i][j - i]  # i를 사용하는 경우

D[i][j] = D[i - 1][j] + D[i][j - 1]

• D[i - 1][j] : 현재 숫자 i를 사용하지 않고 만드는 경우
• D[i][j - i] : 숫자 i를 적어도 하나 이상 사용하여 만드는 경우

for _ in range(T):
    N = int(input())
    print(D[3][N])

• D[3][N]은 1, 2, 3을 사용해서 N을 만드는 오름차순 걍우의 수를 나타낸다.

예시로 N = 4 일떄

가능한 경우는 다음과 같다.

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

총 4가지 → D[3][4] = 4

코드

# 백준 15989 - 1,2,3 더하기 4
# 분류 : 다이나믹 프로그래밍
 
T = int(input())
 
D = [[0] *  10001 for _ in range(4)]
D[0][0] = 1
for i in range(1, 4) :
    for j in range(10001) :
        D[i][j] = D[i - 1][j]
 
        if j >= i :
            D[i][j] += D[i][j - i]
        
for _ in range(T) :
    N = int(input())
 
    print(D[3][N])