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

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

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

---

🗒 코드

import sys
input = sys.stdin.readline

t = int(input())

dp = [1] * 10001

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

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

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

 

---

🤔 후기

여느 1, 2, 3 문제처럼 순열 문제인 줄 알고 짰는데 답이랑 전혀 관계없는 결과가 도출돼 다시 문제를 읽어보니 다음을 간과하고 있었다.

합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

 

1, 2, 3 문제들은 점화식만 잘 세우면 됐기 때문에, 각각의 경우의 수를 정리해 봤다.

• 1 - 1
• 2 - 1+1; 2
• 3 - 1+1+1; 2+1; 3 
• 4 - 1+1+1+1; 2+2; 2+1+1; 3+1  
• 5 - 1+1+1+1+1; 1+1+1+2; 2+2+1; 2+3; 1+1+3 
• 6 - 1+1+1+1+1+1; 1+1+2+2; 1+1+1+1+2; 1+2+3; 1+1+1+3; 2+2+2; 3+3
• 7 - 1+1+1+1+1+1+1; 1+1+1+1+1+2; 1+1+1+2+2; 1+2+2+2; 1+1+2+3; 1+1+1+1+3; 1+3+3; 2+2+3

1의 경우에는 1개, 2의 경우 2개, 3의 경우 3, 4는 4, 5는 5개, 6은 7개, 7는 8개의 경우의 수가 도출되어 다른 문제들처럼 점화식을 세우기가 힘들어졌다.

 

결국 다른 블로그를 참고했다.

1만 써서 합이 되는 경우는 모두 한 가지씩 가지고 있다. 때문에 dp 배열을 초기화할 때 1을 넣어놓는다.

그다음은 2, 3을 조합하는 경우를 고려해봐야 한다.

각각의 경우의 수를 순회하면서 2가 추가되는 경우, 3이 추가되는 경우를 생각해 보면 되는 문제였다.

즉, 2의 경우의 수가 보일 것이다. 1+1, 2의 경우의 수인 경우다.

여기에 3을 추가하면 3의 경우의 수가 된다. 1+1+1, 2+1, 3.

또 3의 경우의 수에 2만 추가하면, 4의 경우의 수가 완성된다.

이런 경우들만 고려하면 되는 것이었다. 이건 경험의 문제라고 생각한다... 더 많이 풀어봐야겠지...🤓