백준: 9095 1, 2, 3 더하기

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

9095번: 1, 2, 3 더하기

 

문제 풀이

 이전에 풀었던, 11726 2xn 타일링, 11727 2xn 타일링 2과 같이 어떠한 경우의 수가 있는지 파악하는 것이 중요하다. n에 따라 발생할 수 있는 경우의 수는 다음과 같다.

 

• n = 1 (1개)
  • 1
• n = 2 (2개)
  • 1 + 1, 2
• n = 3 (4개)
  • 1 + 1 + 1, 1 + 2, 2 + 1, 3
• n = 4 (7개)
  • 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 2 + 2, 1 + 3, 3 + 1
• n = 5 (13개)
• n = 6 (24개)

위와 같은 경우의 수를 가지게 되며, 점화식 `f(n) = f(n - 1) + f(n - 2) + f(n - 3)`을 이끌어 낼 수 있다.

 

 

코드

if __name__ == '__main__':
    for _ in range(int(input())):
        target = int(input())
        cases = [1, 2, 4]
        for i in range(3, target):
            cases.append(sum(cases[-3:]))
        print(cases[target - 1])