[DP] 11726 2*n 타일링 (실버3) with Python

너무 오랫동안 코딩에 손을 땐 상태여서 그런지 많이 실력이 줄었다.

그래서 일단 간단한 문제로 시작해 볼까 한다. => 점차 실버 -> 골드로 넘어가볼려고 한다.

목표는 코테를 그것도 네카라쿠배당토 되는 회사들의 코테를 무난하게 합격해 면접까지라도 가는 것이 목표이다.

문제

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

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

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

dp의 대표적인 문제인 타일링 문제라고 생각한다.

일단 dp이니 규칙이 있는지를 찾아보자

만약 n = 1 이라면 경우의 수는 세로인 경우 하나일 것이다.

만약 n = 2 이라면?

=> 세로로 2개를 만들거나 가로로 두개를 만드는 방법으로 2가지가 나온다

n = 3 이라면?

=> 여기서부터 중요한게 3이란 얘기는 2*n 즉 블럭 1개나 2개로 만들수 있는 w의 사이즈를 벗어 났다는 의미이다.

만약 n=2의 경우에서 딱 세로블럭을 하나만 추가하면 n=3의 케이스를 만족 시킬 것이다.

또한 n=1처럼 모든 블럭을 세로로 쌓는 케이스도 될 것이다.

이것을 쓰면

dp[3] = dp[1] + dp[2]

이렇게 될 것이다.

이것으로 점화식을 생각해보면

dp[n] = dp[n-1] + dp[n-2]

이런 꼴이 될 것이다.

전체 코드

import sys
input = sys.stdin.readline
n = int(input())
dp = [0 for _ in range(1001)]
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
    dp[i] = (dp[i-1]+dp[i-2])%10007
print(dp[n]%10007)