백준 15988번 1, 2, 3 더하기 3 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 15988 1, 2, 3 더하기 3

15988 1, 2, 3 더하기 3

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

15988번: 1, 2, 3 더하기 3

 

정수 n을 1, 2, 3의 합으로 표현해야 한다. 표현하는 방법이 어느 정도 규칙적인 것 같아 규칙을 찾아 풀이하기로 했다.

 

알고리즘 분류

• 다이내믹 프로그래밍

---

소스코드

import sys
input = sys.stdin.readline

dp = [1,2,4,7]
for i in range(int(input())):
    n = int(input())
    for j in range(len(dp), n):
        dp.append((dp[-3]+dp[-2]+dp[-1])%1000000009)
    print(dp[n-1])

---

풀이

N	1	2	3	4	5
경우의 수	1	2	4	7	13

위의 표는 n에 따른 경우의 수들을 계산한 표이다. 초반에는 규칙을 찾기 힘들지만 n이 4 이상일 때 이전 3개의 경우의 수의 합이 현재의 경우의 수라는 점을 알 수 있다.

이를 이용해 문제에 제시된 dp를 모두 구해놓고 답을 출력할 수 있지만 필자가 정리한 방식은 n을 받으면 다시 계산하여 출력하는 방식이다.

dp에 미리 4까지의 경우의 수를 지정하고 4 이상일 때 값들을 계산하는 for문을 이용해 dp[-1] = (마지막 dp) dp[-2] = (맨 뒤에서 2번째 dp), dp[-3] = (맨 뒤에서 3번째 dp) 값들을 활용하여 1,000,000,009로 나누어 dp에 넣어준다.

마지막으로 맨 마지막 dp를 출력하면 해를 구할 수 있다.

 

dp[n-1]로 값을 출력해야 한다. 이유가 있겠지만 dp[-1]로 출력하면 틀렸다는 문구를 출력한다. 

---

풀이 결과

15988 풀이 결과