[DP] 백준 15989번 : 1,2,3 더하기 4 - 파이썬 Python

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

15989번: 1, 2, 3 더하기 4

 

 

n을 1,2,3의 합으로 나타내는 개수는 이전 수를 1,2,3의 합으로 나타냈을 때의 수에 영향을 받는다

dp방법으로 풀어내기로 한다

 

중복되는 1 2 1 / 1 1 2 같은 조합을 없애기 카운팅 안하기 위해서는 

각각의 조합에서 대표만 카운팅해야 함

1 1 2 같은 경우만 카운팅 하기 위해서는

1을 사용하는 방법과 2를 사용하는 방법을 순차적으로 dp를 이용해야 함

 

오름차순으로 줄세워서 대표를 골라낸다고 한다면

1. 1을 사용했을 때, 1 ~ 10001 를 1로 구성하는 방법을 dp 배열에 저장
2. 2를 사용했을 때, 2 ~ 10001 를 2를 포함하는 구성하는 방법의 수를 dp 배열에 저장 (1번 방법을 기반으로)
3. 3을 사용했을 때, 3 ~ 10001 를 3을 포함하는 구성하는 방법의 수를 dp 배열에 저장 (2번 방법을 기반으로)

 

 

 

n = int(input())

dp = [1] * 10001

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


        

for i in range(n):
    a = int(input())
    print(dp[a])

 

 

백준 강의를 들으며 정리한 내용

 

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

9095번: 1, 2, 3 더하기

 

1,2,3 더하기 문제 같은 경우에는 본문제와 달리 중복을 허용한다. 

dp[0] 을 1이라 설정하고 

3을 만들기 위해서는(dp[3]) 

아무것도 없는 경우 즉, 3을 만들기 위해 3만 더하면 되는 경우 (dp[0])

1이 되는 경우 즉, 3을 만들기 위해 2만 더하면 되는 경우 (dp[1])

2가 되는 경우 즉, 3을 만들기 위해 1만 더하면 되는 경우 (dp[2])

dp[3] = dp[0] + dp[1] + dp[2] 가 점화식이었다.

 

따라서 본 문제(15989)와 for 문의 순서가 변한 문제라고 보면 된다

 

import sys

n = int(input())

dp = [0] * 10001
dp[0] = 1

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


        

for i in range(n):
    a = int(input())
    print(dp[a])