[알고리즘] 백준 11726 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로 나눈 나머지를 출력한다.

 

해결코드

n = int(input())

li = [0 for _ in range(n+1)]

if n <= 3 : print(n)
else : 
	li[1] = 1
	li[2] = 2
	for i in range(3, n+1):
		li[i] = li[i-1] + li[i-2]

	print(li[i]%10007)

문제풀이

n=1일 때 경우의 수 1

n=2일 때 경우의 수 2

n=3일 때 경우의 수 3

n=4일 때 경우의 수 5 ....

경우의 수가 피보나치 수열과 같은 것을 볼 수 있다.

그렇다면 점화식은 li[n] = li[n-1]+li[n-2] 이다.

코드를 보면 먼저 n에 수를 입력받아준다.

그리고 n+1개 만큼 원소 0을 가진 li라는 리스트를 만들어준다.

n이 1,2,3일 경우에는 어차피 경우의 수도 1,2,3이므로 그대로 출력해주면 되고

n이 그 이상일 경우에는

li[1]과 li[2]를 선언해주고

for문을 3부터 n까지 돌려준다.

그리고 아까 구한 점화식대로 반복문을 돌려주면 원하는 값이 나오는데

그 값을 10007로 나눈 값을 출력해주면 된다.