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

문제

 

풀이

1. 모든 정수(n)는 1만 써서 구할 수 있다.

 

n	경우의 수
0	없음
1	1
2	1 + 1
3	1 + 1 + 1
4	1 + 1 + 1 + 1
5	1 + 1 + 1 + 1 + 1

 

1의 합으로 정수 n을 나타내는 방법은 1가지 이므로 dp를 전부 1로 초기화한다.

dp = [1] * 10001

 

2. 1, 2의 합으로 정수 n을 나타내는 방법은 (n - 2)를 1의 합만으로 나타낸 방법에 2를 더해주면 된다.

n	경우의 수
0	(없음)
1	1
2	1 + 1, (없음) + 2
3	1 + 1 + 1, 1 + 2
4	1 + 1 + 1 + 1, 1 + 1 + 2
5	1 + 1 + 1 +1 + 1, 1 + 1 + 1 + 2

 

3. 1, 2, 3의 합으로 정수 n을 나타내는 방법은 (n - 3)을 1, 2의 합으로 나타낸 방법에 3을 더해주면 된다.

표 생략

코드

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]
    
t = int(input())

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

 

마무리

언제쯤 dp가 만만해질까...

그런 날이 올까?