[ BOJ / 파이썬 ] 11726 2xn 타일링

사실 수학적 센스가 필요한 문제라 처음 만나면 풀어낼 자신은 없다.

대신 해설을 보고나면 구현 자체는 어렵지 않다.
DP문제는 많이 풀어보는 것이 힘! 코딩테스트는 경험이 힘!

 

해당 문제는 일단 DP로 풀 수 있다는 것을 알아채기도 까다로운 것 같다.

그런데 점화식을 세우는게 진짜 아리송하다.

 

다만 우리에게 주어진 경우의 수가 사실은 몇 개 되지 않는다는 사실, 배치가 중복된다는 사실을 파악하면 되는 문제다.

 

2 x 1

1 x 2

 

를 놓는데, dp테이블을 dp[i] 가 2 x i 를 채우는 방법의 수라고 할 때, dp[1] = dp[n-1] 이다. 왜? 

2 x n 바닥에서 2 x 1을 뺐으니 남은 건 2 x (n-1) 바닥이기 때문에. 2 x (n-1) 바닥을 채우는 수와 같기 때문.

 

1 x 2 의 경우도, 1 x 2 써야하는 상황에서 2 x 2 채우려면, 어차피 해당 타일 2개 쓰는 방법밖에 없으므로 2 x 2메꿔지고,

위의 경우와 마찬가지로 dp[2] = dp[n-2] 가 되는 셈.

 

따라서, dp[n] = dp[n-1] + dp[n-2]로 (2 < n) 점화식이 나오는데, 시작 두 경우 말고는 저렇게 타일 놓는 방법이 경우에 따라 중복되어서 계속 나오기 때문이다. (이게 처음에 이해가 잘 안 갔으나 작은 수로 생각해보면 이해된다.)

 

 

 

/  1번째 제출  /

import sys
input = sys.stdin.readline

n = int(input())

d = [0]*n

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

: 하하 드디어 이해했다고 신나서 풀었는데 무려 런타임에러가 나서 틀렸다.

: 도대체..? 싶어서 문제토론방을 봤는데, DP의 기본사항에 대해서 신경을 쓰지 않았다.

 

: 바로 초기값에 대한 예외 처리. for문에서 2부터 시작하며 아 예외처리했구나라고 여기고 넘겼다.

: 해당 코드에서 하지만, n이 1로 들어올 경우 d[1]에 접근할 수가 없다. 그래서 인덱스 에러가 난 것이다.

 

: 그 오류를 고쳐서 다시 제출했다.

 

 

 

/  2번째 제출  /

import sys
input = sys.stdin.readline

n = int(input())

d = [0]*n

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