BOJ 11726

Input

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

import sys
input = sys.stdin.readline

n = int(input())

DP

처음 접근했던 방식은 다음과 같다.

나름 찾았던 조건과 규칙성이,

• 가로 막대를 놓으면 밑에도 가로여야 하며, 얘네는 마치 세로 막대가 2개 묶인 것처럼 취급한다. 따라서, 세로 막대 개수를 n - i 인 것처럼 생각한다.
• 전체 n - i 개의 막대 중에서 i 개의 가로 막대를 고른다. 즉, 조합처럼 생각해서 (n-i)C(i) 를 cnt에 더한다.

그래서 다음과 같이 코드를 짰다.

ava = n // 2

def factorial(i):
  if i < 2:
    return 1
  
  return i * factorial(i-1)

# 가로 막대 i개
for i in range(ava+1):
  if i == 0:
    cnt += 1
  elif n - i < i:
    cnt += 1
  else:
    div = 1
    for k in range(i):
      div *= (n - i - k)
    cnt += div / factorial(i)

근데 틀림.

답은 간단하다.

n을 1부터 체크해나가면 다음과 같은 규칙성을 보인다.

"""
n = 1 -> cnt = 1
n = 2 -> cnt = 2
n = 3 -> cnt = 3
n = 4 -> cnt = 1+1+3 = 2+3 = 5
n = 5 -> cnt = 1+4+3 = 5+3 = 8
"""

따라서, 점화식은 다음과 같다.

점화식: cnt[i] = cnt[i-1] + cnt[i-2]

이걸 그대로 코딩하면 된다.

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

여기서 덧붙이면, DP는 배열을 사용하기 때문에 index out of list Error가 잘 날 수 있다.

따라서, 그냥 배열 크기를 문제에 주어진 최대 범위로 설정해놓자.

Output

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

print(cnt[n] % 10007)