11726 - 2 x n 타일링

 

---

문제 (S3)

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

11726번: 2×n 타일링

 

 

풀이

DP의 정수, 타일링 문제이다. 예전에도 풀었지만 100프로 이해한다는 느낌이 아니었는데, 이 참에 다시 풀어봤다.

 

우리는 1*2 의 타일과 ( ㅡ ) 2 * 1 타일을 사용할 수 있다. ( | ) 

해당 타일들을 이용하여 2 * n 의 타일을 채워야한다.

 

여기서 우선 생각해야할것중 하나는 1 * 2 타일을 사용하기 위해서는 항상 2개를 세트로 사용해야한다. ( = )

 

경우의 수를 생각해보면

 

Case 1 -   ' | '

 

Case 2 - ' || '  ' = '

 

Case 3 - ' ||| '  ' =| '  ' |= '

 

Case 4 - ' |||| '  ' =|| '  ' |=| '  ' ||= '  ' == '

 

이정도로 볼 수 있다.

 

설명전에 답을 먼저 말하면 (D[n]이 2*n개의 타일링을 만드는 경우의 수 일때) D[n] = D[n-2] + D[n-1] 이다.  

물론 D[1] = 1, D[2] = 2 로 초기화 해주고 시작한다.

 

그럼 D[3]일때 보자

 

우리는 타일을 추가할경우 1*2, 2*1 타일을 사용해야한다. 가로의 길이가 2이고, 1인 타일들이다.

 

Case 3 을 잘보면 Case 2 에서 가로길이가 1인 타일들을 추가해줬고, 경우의 수에 들어갔다.

그리고 Case 1 에서 가로길이가 2인 ' = ' 타일을 추가해줘서 경우에 수에 추가해줬다.

 

Case 4의 경우에도 확인해보면 Case 3 일때 2*1인 타일들을 추가해줬고, Case 2 일때 1*2 타일들을 추가해줘서 경우의 수에 넣어주었다. 가로길이가 2이고, 1인 타일들이기 때문에 2나 3에서 4로 가는 경우의 수를 만들 수 있는 것이다.

 

앞서서 경우의 수를 모두 저장해뒀고, 가로길이에 따라서 들어갈 수 있는 타일의 종류가 명확하기 때문에 이와 같이 풀이 할 수 있다.

 

 

코드

n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 2

for i in range(3, 1001):
    d[i] = (d[i-1] + d[i-2]) % 10007
print(d[n])

 

후기

해당 문제가 예전엔 잘 이해가 안됐는데, 시간이 지나고 설명들을 찾아보니 이해가 되었다. DP는 여러모로 참 신기하다.