[알고리즘/DP] 15989번 : 1,2,3 더하기 4 - python

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

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

 

---

• 문제
• 소요시간: 7분 30초

---

• 설계하기(접근방법) 

1. 입력받기

테스트 케이스와

숫자를 입력받는다

 

2. 구현하기

이전에 풀었던 dp문제와 같다

 

1~10000까지

1으로 채우는 방법은 전부 1이다

 

1 ~ 10000까지

2로 채우는 방법은

1: 1

2: 1+1 2

3: 1+1+1, 1+2

4: 1+1+1+1 1+1+2 2+2

 

규칙성을 찾아보면

현재 항에다가 2번째 전의 항에서

모두 +2를 해준 값을 가져오는 것과 같다

 

3역시 마찬가지다

 

1: 1

2: 1+1 2

3: 1+1+1, 1+2, 3

4: 1+1+1+1, 1+1+2, 2+2 1+ 3

5: 1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 2+ 3

 

 

 

3. 출력하기

입력받은 dp를 출력한다

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

dp = [1] * 10001
dp[0] = 1
for i in range(2, 10001):
    dp[i] = dp[i] + dp[i - 2]

for i in range(3, 10001):
    dp[i] = dp[i] + dp[i - 3]

 
for _ in range(int(input())):
    print(dp[int(input())])

---

• 얻어갈 부분

1. 이전의 문제의 응용이라 쉽게 풀 수 있었다