[백준] 9095 - 1, 2, 3 더하기

아이데이션

앞서 풀었던 2xn 타일링 문제를 1x1 타일링 문제처럼 바꾸면 쉽게 풀 수 있다

사실 이렇게 쉽게 생각할 수 있는 이유는 순서가 고려되어서 1 + 1 + 2와 2 + 1 + 1이 다른 경우의 수로 세어지기 때문이다

아무튼! 고려할 수 있는 경우의 수는 다음과 같다!

1. i - 1에서 1 더하기

2. i - 2에서 2 더하기

3. i - 3에서 3 더하기

이렇게 해서 i번째 경우의 수는 (i - 1의 경우의 수) + (i + 2의 경우의 수) + (i - 3의 경우의 수)로 업데이트 할 수 있다

 

풀이

t = int(input())

for _ in range(t):
    n = int(input())
    cache = [i for i in range(n + 1)]
    cache[0] = 1

    for i in range(3, n + 1, 1):
        cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]

    print(cache[n])