[Python][백준] 15989. 1, 2, 3 더하기 4 / DP

링크🔗

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

---

🗒️파이썬 코드 풀이

N = int(input())

dp = [1] * 11000
print(dp[0:11])

for i in range(2,11000):
    dp[i] = dp[i] + dp[i-2]

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

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

 

1. DP로 푸는 문제이다. 

 

2. 0~11000까지 넉넉히 DP 리스트를 만들어 준다.

 

3. 입력값을 쪼개었을 때, 2가 나오는 수를 누적시켜준다.

 

4. 2를 누적시킨 리스트에, 3이 나오는 수를 누적시준다.

 

5. DP 리스트가 만들어졌으므로, 입력 값을 dp 인덱스에 넣으면 원하는 출력을 얻을 수 있다.

 

ex) DP 0~10까지 누적
1이 되는 수 누적 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2가 되는 수 누적 : [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
3이 되는 수 누적  : [1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14]

1 누적 -> 2 누적 -> 3누적 이런식으로 누적값을 계속 쌓아간다.

 

📌  문제 코멘트

처음에는 그리디 문제인가 했는데, DP 문제였다.

문제 구현이 어렵거나 하지는 않다.

다만 [i] + [i-2] , [i] + [i-3] 의 점화식을 생각해내는게 쉽지 않다.

---

📚문제

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

예제 입력 1 복사

3
4
7
10

예제 출력 1 복사

4
8
14