[Silver III] 2×n 타일링 - 11726

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
anslist = [0]*n
anslist[0] = 1

if n>=2:
  anslist[1] = 2
  for i in range(2,n):
    anslist[i] = anslist[i-1] + anslist[i-2]
print(anslist[n-1]%10007)

dp 배열만들기
anslist = [0]*n

초기값 설정
anslist[0] = 1 anslist[i]는 2×(i+1) 직사각형을 채우는 방법의 수를 저장한다. n=1일 때는 한 가지 방법밖에 없다. (2×1 타일 하나)
if n >= 2: anslist[1] = 2 n=2일 때는 두 가지 방법(가로 1×2 두 개, 세로 2×1 두 개)이 있다.

for i in range(2, n): anslist[i] = anslist[i-1] + anslist[i-2]
2×n 직사각형을 채우는 방법은 2×(n-1) + 2×(n-2)의 조합이다.

분류

다이나믹 프로그래밍

제출 일자

2025년 3월 25일 12:34:23

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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