[Python 3] BOJ - 9095 "1,2,3 더하기"

 # 문제 링크 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 # 풀이 :

개인적으로 이 문제의 핵심은 중복되는 경우를 생각하지 않는다는 점이다. 또한 이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 왜냐하면 i를 1,2,3의 합으로 나타내기 위해서는 i - 1, i - 2, i - 3번째의 경우의 수를 알아야 하기 때문에, Subproblem으로 나눌 수 있으며, 각각이 종속적이기 때문이다. 점화식은 아래와 같다. 

 왜냐하면 i - 3의 경우 3을 더하면 i가 되는데, 각 경우에 단순히 + 3을 붙이기만 하면 되므로 전체 경우의 수에는 영향을 미치지 않고, i - 2, i - 1도 마찬가지이기 때문이다. 또한 중복을 허용하기 때문에 추가적인 작업이 필요 없다.

 

 # 코드

import sys
total = int(sys.stdin.readline())

d = [-1] * 12
ans = []

# 경계값들은 직접 예외 처리
d[1] = 1
d[2] = 2
d[3] = 4

# 점화식
for i in range(4, 12):
    d[i] = d[i - 1] + d[i - 2] + d[i - 3]
d = d[1:]
for i in range(total):
    temp = int(sys.stdin.readline())
    ans.append(d[temp - 1])
for i in ans:
    print(i)