[백준] 11726 : 2×n 타일링 (파이썬 / Python)

2×n 타일링

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

11726번: 2×n 타일링

---

문제

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

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

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

2

예제 입력 2

9

예제 출력 2

55

---

코드

import sys
input = sys.stdin.readline

n = int(input())
d = [0] * 1001

d[1] = 1
d[2] = 2

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n] % 10007)

풀이

위 문제는 동적계획법의 bottom-up 방식으로 풀 수 있다. 그 이유는 작은 문제를 풀고 이 값을 저장하여 큰 문제에 활용 가능하고, 초기값을 알고 있기 때문이다.

코드의 첫 두 line의 경우 아래의 참고에 정리해두었다.

2×n 크기의 직사각형을 채우는 방법의 수를 d라는 배열에 저장할 것이고, 이 배열은 0의 값으로 채우며, 문제에서 주어진 입력의 최댓값의 크기로 배열을 생성하였다.

d[1]인 경우는 채울 수 있는 경우가 1가지, d[2]인 경우는 2가지 있기 때문에 초기값을 미리 지정해두었다.

위 문제를 풀기 위해서 n = 1, n = 2, n = 3, n = 4인 경우까지 구하여 점화식이 d[i] = d[i-1] + d[i-2]임을 알 수 있었으나 해당 점화식이 나온 이유를 정확하게 파악하고자 이 블로그(https://cijbest.tistory.com/20)를 참고하였으며, 아래 나오는 사진의 출처 모두 해당 블로그에서 가져왔다.

이는 n = 4까지의 경우의 수를 따져본 것이다.

n = 3부터 보면 n = 1과 n = 2의 타일 모양이 그대로 들어있고,

n = 4를 보면 n = 2와 n = 3의 타일 모양이 그대로 들어있어 위와 같은 점화식의 결론을 낼 수 있다.

---

참고 | sys.stdin.readline

sys.stdin.readline은 입력값 시간을 줄여주는 코드이다. 보통의 알고리즘 풀이는 아래와 같이 입력값을 받아서 문제를 푸는 구조이다. 

n = input()

 

기능상에는 큰 차이가 없지만 아래와 같이 입력값을 받으면 속도 차이가 크다. 즉, input으로 작업한 코드가 시간 초과가 났을 때, sys.stdin.readline()을 input에 저장해주고, input으로 작업한다면 정답처리가 될 확률이 크다.

import sys
input = sys.stdin.readline()

n = int(input())

 

 

위 참고는 https://puleugo.tistory.com/42 를 참고하여 작성하였습니다.