BOJ 9095

Input

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

import sys
input = sys.stdin.readline

for _ in range(int(input())):
  n = int(input())

굳이 t 변수를 생성하지 않아도 됨

Output

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

1	print(ret[n-1])

DP

가장 중요한 건, 규칙성을 파악하는 것이다.

DFS나 BFS와는 다르게 DP는 규칙성을 파악하는게 더 어려운 것 같다. 무조건 반복이 아니라 규칙에 따라 기존의 값을 활용해야 하기 때문인가…

이 문제도 규칙성을 파악하면 점화식을 만드는 건 하나도 어렵지 않음.

예를 들어n = 4 라고 한다면,

"""
규칙
1 = 1
2 = 1+1
  = 2
3 = 1+1+1
  = 2+1
  = 1+2
  = 3
4 = 1+1+1+1 => 3 ++1
  = 2+1+1 => 3 ++1
  = 1+2+1 => 3 ++1
  = 1+1+2 => 2 ++2
  = 2+2 => 2 ++2
  = 3+1 => 3 ++1
  = 1+3 => 1 ++3
"""

결국 1,2,3으로 숫자를 만들어야 하니 1,2,3 자체만 default로 경우의 수를 배열에 세팅해놓은 다음 이를 토대로 4부터 조합을 찾아가면 된다.

4의 경우 3의 모든 경우에 +1씩 하면 되고 (4 = 3+1 이니,) 2에 +2씩, 1에 +3씩 하면 된다. 즉, 점화식은 다음과 같다.

1	ret[n] = ret[n-1] + ret[n-2] + ret[n-3]

코드는 다음과 같다.

ret = [1, 2, 4]

for i in range(3, n):
  ret.append(ret[i-1] + ret[i-2] + ret[i-3])