[python] 백준 알고리즘 9095번 1,2,3 더하기 풀이 소스

계산하다보니 입력한 케이스에 대해 입력한 케이스의 3가지 케이스의 경우의 수를 다 더하니

현재 입력한 케이스의 경우의 수가 나왔다. (귀납법적인 결론 도출..)

그래서 생각해보니 현재 케이스의 바로 직전(-1)의 케이스의 경우는 '1'을 더해주기 전의 총 케이스를 구한 값과 같다.

그리고 2번째 전의 케이스(-2)의 경우 '2'를 더 해주기전의 총 케이스를 구한 값과 같다.

3번째 전의 케이스(-3)의 경우 '3'을 더 해주기전의 총 케이스를 구한 값과 같다. 

* 1이 왔을 때 n의 케이스 = 1 + (n-1)의 값을 구하기 위한 총 케이스

* 2가 왔을 때 n의 케이스 = 2 + (n-2)의 값을 구하기 위한 총 케이스

* 3이 왔을 때 n의 케이스 = 3 + (n-3)의 값을 구하기 위한 총 케이스

이란 결과가 나온다.

예를 들어, 5를 입력한다면,

* 1 +가 되었을 때 5의 케이스 = 1 + 4의 총 케이스

* 2 + 가 되었을 때 5의 케이스 = 2 + 3의 총 케이스

* 3+ 가 되었을 때 5의 케이스 = 3 +2의 총 케이스

5의 총 케이스는 4의 총 케이스 + 3의 총 케이스 + 2의 총 케이스이다. 

그럼 1이 오거나 2가 오거나 3이 오거나 했을 때 그 수를 제외한만큼의 총 경우의 수를 구할 수 있다.

코드는 아래와 같이 만들었다. 

 
t = int(input())
 
output = []
output.insert(0, 0) # 넣어주지 않으면 list index out of range 에러가 뜸
output.insert(1, 1) # 1을 넣을 경우 경우의 수 1가지(1)
output.insert(2, 2) # 2를 넣을 경우 경우의 수 2가지(1+1, 2)
output.insert(3, 4) # 3을 넣을 경우 경우의 수 3가지 (1+1+1, 1+2, 2+1, 3)
 
for i in range(0, t):
    n = int(input())
    for j in range(4, n+1):
        output.insert(j, output[j-1] + output[j-2] + output[j-3])
    print(output[n])