백준 11726번 바로가기

나의 풀이

# 입력
import sys
read = sys.stdin.readline

arr = [1, 2, 3] + [0]*1000

# 처리
for i in range(n:=int(read().strip())):
  arr[i+2] = (arr[i+1] + arr[i]) % 10007

print(arr[n-1])

CODE REVIEW

  1. (1*2) 한 개 또는 (2*1) 위아래로 두 개 쌓는 방식을 택할 수 있어서, n을 1, 2의 합으로 나타내는 경우의 수를 구하는 문제로 바뀐다.
  2. 점화식은 $a_{n+2} = a_{n+1} + a_{n}$ n+1에 (1*2) 한 개 넣거나, n에 (2*1) 위아래로 두 개 넣는 경우의 합으로 계산할 수 있다.
  3. cf) 피보나치 수열과 동일.