백준 11726 : 2xn 타일링Permalink

https://www.acmicpc.net/problem/11726

문제Permalink

1 2

풀이Permalink

점화식 찾기Permalink

  • 이 문제는 다이나믹 프로그래밍 기법을 활용하여 푸는 문제이다.
  • 대부분의 문제와 같이 이 문제 또한 점화식을 사용하여 풀 수 있다.

규칙 찾기Permalink

3

  • 위 그림과 같이 수열 An의 n이 1씩 증가할 때마다 가로 1 * 세로 2와 가로 2 * 세로 2 사각형에 각각 n-1항의 타일 모양과 n-2 항의 타일 모양이 오른쪽에 붙는 형태로 n 항의 타일 모양이 결정된다.
  • 예를 들어 n = 4일 때의 경우 가로 1 * 세로 2 타일의 오른쪽에 n = 3일 때의 타일 모양이 그대로 붙어 3개, 가로 2 * 세로 2 타일의 오른쪽에 n = 2일 때의 타일 모양이 그대로 붙어 2개가 더해진다.
  • 따라서 점화식을 구하면
    An = An-1 + An-2 (단, A >= 3일 때)가 된다.



완성된 코드Permalink

import sys
input = sys.stdin.readline
n = int(input())
arr = [[] for _ in range(1001)]
arr[1] = 1
arr[2] = 2
for i in range(3, 1001):
arr[i] = arr[i-1] + arr[i-2]
print(arr[n] % 10007)
view raw 11726 hosted with ❤ by GitHub

댓글남기기

참고