백준 알고리즘 - 1,2,3 더하기 (9095) [Python]

 문제

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

 

 문제 상황

 

- 입력받은 정수 N을 숫자 1,2,3의 합을 이용해서 표현할 수 있는 방법의 수를 구한다.

 

 

 

 

 

 해결 전략

 

- N을 표현하는 방법의 수는 N-1을 표현하는 방법에 1을 더하거나, N-2를 표현하는 방법에 2를 더하거나, 아니면 N-3을 표현하는 방법에 3을 더하는 경우이므로 항이 3개인 피보나치가 된다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    cache = [0,1,2,4] + [0]*(N-3)
    for i in range(4, N+1):
        cache[i] = cache[i-1] + cache[i-2] + cache[i-3]
    
    print(cache[N])

 

 

 

 

 

 해설

 

- 상황을 그림으로 그려보면 공통점을 발견할 수 있다. 뒤에 더해주는 값은 1,2,3만 가능하고 각각의 케이스는 or의 상황으로 묶여 겹치는 것이 없으므로 피보나치처럼 작동한다. 1,2,3을 앞으로 더해주는 상황은 결국 다른 케이스에 포함되어 있으므로 신경쓸 필요가 없다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 손으로 상황을 그려보며 규칙성을 발견했다.