[BOJ] 11726 2xn 타일링 Python

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

11726번: 2×n 타일링

 

2×n 타일링 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

139353

53351

39451

36.176%

문제

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

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

입력

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

출력

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

풀이 코드

import sys
input = sys.stdin.readline

graph = [[] for _ in range(1001)]
graph[1] = 1
graph[2] = 2
n = int(input())
for i in range(3, n+1):
    graph[i] = graph[i-1]+graph[i-2]
print(graph[n]%10007)

DP문제를 드디어 혼자 풀었다 !!

문제를 보면 정사각형을 만드는 방법은 두가지가 있다.

세로를 두개 불이거나 가로를 두개 붙이거나

여기서

1. 새로를 두개 붙이는 경우는 n-1에 세로를 하나 붙여주는 것

2. 가로를 두개 붙이는 경우는 n-2에 가로두개 붙인걸 붙여주는 것

이다.

 

출처 : https://assb.tistory.com/entry/%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81

따라서 n번째 경우의 수는 (n-1번째 경우의 수)+(n-2번째 경우의 수)가 되는 것이다 !!

 

DP문제는 규칙을 떠올리는게 어려운데 성취감이 많은 알고리즘 같다. 더 연습해야지.