[Python] 11726 - 2×n 타일링

1. 문제 정의

입력받은 n에 대해 2xn 크기의 직사각형에 1x2, 2x1의 모양을 채워넣는 경우의 수를 구하는 문제이다.

 

2. 풀이 방식

DP 알고리즘을 이용하여 문제를 해결할 수 있다. 먼저 n=1의 경우에 대해 생각해보면 당연히 한 가지 경우 밖에 없다.

그 다음 n=2의 경우에서는 2가지의 경우의 수가 있음을 알 수있다. n=3일 때는 두 가지의 경우로 예시를 들 수 있다.

 

위의 그림과 같이 1x2가 먼저 오는 경우, 2x1가 먼저 오는 경우 두 가지 케이스에 대해서 남은 공간의 경우의 수는 n=2일 때와 n=1일 때이다. 따라서 이를 합한 수가 n=3일 때의 경우의 수가 된다.

 

이후 n=4, n=5 ... 등의 경우도 이와 같은 풀이를 적용하여 해결할 수 있다.

 

코드로 작성하면 다음과 같다.

# 11726 2xn 타일링

n = int(input())
li = [0] * 1001 # n은 1000까지
li[1] = 1
li[2] = 2

for i in range(3, n+1):
    li[i] = (li[i-1] + li[i-2]) % 10007 # 출력 조건

print(li[n])

3. 후기

DP 문제는 여러 번 풀어 보았으나, 여전히 머릿속이 복잡해지는 기분이다. 그림을 이용하여 문제를 해결하니 한결 수월하다는 느낌을 받는다. 하지만 실제 코딩테스트에서는 그림을 그리며 문제를 풀 수 없으니 좀 더 단련해야 겠다는 생각이 든다.