백준 9095번 바로가기

나의 풀이

import sys

read = sys.stdin.readline

arr = [1,2,4] + [0]*12
for i in range(12):
  arr[i+3] = arr[i+2] + arr[i+1] + arr[i]

for _ in range(int(read().strip())):
  print(arr[int(read().strip())-1])

CODE REVIEW

  1. 처음 아이디어는 중복조합에서 칸막이를 세우는 방법을 생각했는데, 1, 2, 3만 사용 가능해서 적용하기에 쉽지 않았다.
  2. 사실 n<=11이기 때문에 11까지 직접 노가다로 구하는 방법도 있겠지만, 코딩 문제 풀이이기 때문에 다른 방법을 생각해보았다.
  3. n이 1부터 6까지에 대한 $a_{n}$ 수열을 구해다가, $a_{n+3} = a_{n+2} + a_{n+1} + a_{n}$ 규칙성을 발견했다.
    • 이 점화식을 분석해보면, (n+3)개의 경우의 수는 (n+2)개에 1을 오른쪽에 붙인 경우 + (n+1)개에 2을 오른쪽에 붙인 경우 + (n)개에 3을 오른쪽에 붙인 경우의 합이다.
    • 반대쪽에 붙이는 경우, case가 겹치기 때문에 중복 counting 되어 안된다.