[백준] 2133번-타일 채우기

도저히 못풀겠어서 답을 보았는데 d[0]값 초기화는 무조건 1로 해줘야 했다.
1X2, 2X1 타일을 채우는 거니까 3X0벽은 당연히 0이지! 라고 생각하면서 풀었는데 오답..
정답코드를 보니 3X0 경우에도 꼭 하나를 채워줘야 해서 d[0]=1 이었다.
왜 ? ? ?? 상식적으로 0칸이면 타일 넣을 칸이 아예 없다는건데 왜 꼭 하나를 채워줘야 하는걸까?
(이유를 아시는 분은 부디 저에게도 알려주세요..복받으실겁니다T_T)

 

문제

 

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

 

풀이과정

 

1.규칙

• dp이므로 점화식과 메모이제이션을 이용합니다.
• 벽은 타일로 꽉 찰수 있는 경우만 생각합니다.

2.순서

 

점화식을 생각해봅니다.

먼저, 1X2, 2X1타일은 짝수벽에만 넣을 수 있으므로 1,3,5..같은 홀수의 경우는 제외합니다.

짝수벽에서만 반복되는 규칙을 찾아봅니다.

3X2의 경우 타일을 채울 수 있는 방법은 112,211,222로 3가지 입니다.

 

3X4 부터는 두케이스로 나눠서 생각해야 하는데, 첫번째케이스는 3X2를 그대로 반씩 붙여서 표현할 수 있는 경우입니다.

실제로 만들어보면 112,211,222 모두 3가지씩 횟수가 늘어나므로

첫번째케이스의 점화식은 d[i] = d[i]+d[i-2]*3 입니다.

두번째는 3X2로 표현할 수 없는 새로운 케이스 입니다.

따라서 점화식은 d[i] = d[i] + d[i-2]*3 + d[i-4]*2로 생각하기 쉽지만, 마저 3X6의 경우도 생각해보아야 합니다.

3X6의 첫번째케이스는 3X4와 마찬가지로 d[i-2]*3 지만, 두번째케이스는 3X4와 달리 d[i-4]*2가 아니기 때문입니다.

그림으로 살펴보면, 두번째케이스 값은 d[i-4]*2 + d[i-6]*2(즉, d[2]*2 + d[0]*2 = 3*2 + 1*2 = 6 + 2 = 8) 인 것을 알 수 있습니다.

결국 d[i]는 d[i-2]*3 과,

d[(i-4)-=2]*2 값을 계속 더해주면 답이 나오게 됩니다.

 

따라서 점화식은

d[i] = d[i] + d[i-2]*3 + d[k]*2(k=i-4, k는 0이 될때까지 -=2) 입니다.

 

3.코드

*d[0]는 꼭 1로 초기화 해줘야 제대로 된 답이 나옵니다.*