[백준/Python] 11727번 : 2×n 타일링 2

문제 정보

제목 : 2×n 타일링 2

번호 : 11727번

사용 언어 : Python

문제 링크

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

11727번: 2×n 타일링 2

 

시간 제한	메모리 제한
1 초	256 MB

 

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

입력

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

 

출력

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

 

입출력 예제

---

나의 풀이

먼저 타일을 채운 개수를 알아내기 위해 n=4까지 그림을 그려봤습니다. n=1일때 1, n=2일때 3, n=3일때 5, n=4일때 11이라는 점을 찾았습니다. 이것을 통해 P(n) = P(n-1) + (P(n-1)*2)이라는 점화식을 도출할 수 있었습니다.

input_n이라는 변수에 값을 입력받아 저장하고, 1과 2는 초기값이기 때문에 if문으로 처리하여 출력했습니다. 이외에는 3부터 input_n+1까지 반복하는 for문을 이용해 점화식을 표현합니다. 반복이 끝나면 dp[input_n]을 10007로 나눈 나머지를 출력합니다.

 

코드

input_n = int(input()) # n 입력받기

dp = [0 for _ in range(1001)]
dp[1] = 1 ; dp[2] = 3 # 2 * n 크기의 타일 초기값 설정해주기
result = 0

if ( input_n < 2) :
    result = dp[input_n] 
else :
    for i in range(3,input_n+1) :
        dp[i] = dp[i-1] + (dp[i-2] * 2) # P(n) = P(n-1) + (P(n-2)*2)
print(dp[input_n] % 10007)