[백준 11726번] 2xn 타일링 (python)

문제

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

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

 

기록

(dp 3일차) 계산을 잘못해서 한참 틀리다가 겨우 맞았다. 아래 결과들이 지저분해서 맞은 결과만 기록해야겠다..ㅎ 세로블럭 1개를 제외한 경우의 수와 가로블럭 2개를 제외한 경우의 수x2(세로2개/가로2개)를 더해서 계산했다가 나중에 세로블럭 1개를 제외한 경우의 수와 세로블럭 2개를 제외한 경우의 수가 겹친다는 사실을 알게되서 수정했다. 혹시 도움이 될까 해서 n 10까지의 결과를 적어놓는다. 

[0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

이 문제는 2xn의 직사각형을 채우는 방법의 수를 저장한 배열 dp를 사용하여 dp[n]=dp[n-1]+dp[n-2]의 점화식을 세워 풀면 된다. 세로블럭 1개를 제외한 경우의 수와 가로블럭 2개를 제외한 경우의 수를 더한 식이다. 참고로 10007로 나누어 결과 제출해야한다!

 

코드

n = int(input())
dp = [0, 1, 2]
for i in range(3, n+1):
    dp.append(dp[i-1]+dp[i-2])
print(dp[n]%10007)

1. 2xn의 직사각형을 채우는 방법의 수를 저장한 배열 dp를 만든다. 2x1일 때와 2x2일 때는 초기화 시켜놓는다.

2. 3부터 dp[i-1](세로블럭 1개 제외)와 dp[i-2](가로블럭 2개 제외)의 방법 수를 더한 값을 저장한다.

3. 2xn의 결과를 10007로 나눠 출력한다.