[백준/Python] 2133 타일 채우기

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

2133번: 타일 채우기

 

2 X N 타일 채우기에서 활용했던 방법을 그대로 적용해 보았다.

3X2의 경우 예제에 결과가 나와있으므로,

이를 토대로 3X3을 순차로 구해보았으나 N이 홀수인 경우엔 성립이 불가하다는 것을 발견했다.

그래서 짝수를 기준으로 그림을 그리며 점화식을 세웠다. 

3X2

 

 

문제는, 각 케이스마다 예외가 있다는 것이었다. 

3X4의 경우, 3X2의 경우의 수 * 3을 하면 된다고 생각했지만 3X4에서만 나올 수 있는 예외 케이스(빨간 체크)가 있었다.

3X4

 

 

그래서 dp[4] = dp[2]*3 + 2라는 조건을 성립했다.

 

여기까지가 끝인줄 알고 코드를 작성했으나 실패...

규칙 찾는 것이 어려워 블로그와 백준님의 강의를 참고하였다. 

 

3X6..8..10.. 등으로 수가 늘어나면서 예외 케이스는 4의 경우처럼 각각 2개씩 늘어간다는 것을 확인했다. 

(4의 예외케이스와 비슷한 형상으로 늘어남)

그리고 3X6의 경우 3X4으로 타일을 채운 나머지, 즉 3X(6-4)(dp[2])의 경우의 수를 구해서 더해야 한다.

(3X2타일이 각각 좌우로 위치하는 경우가 있으므로 X2를 해줘야 함!)

파란 부분(3X2)의 위치가 다른 경우

 

 

8, 10의 경우도 마찬가지인데, 

이때 3X6, 3X4를 채운 경우의 수 또한 모두 합해준다. 

(여기서 아직도 이해가 안됨...^^) 

 

이 조건을 따라 점화식을 세워보면 아래와 같다. 

dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2])*2 + 2

 

n = int(input())
if n % 2 == 1:
    print(0)
    exit()

dp = [0] * (n+1)

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


for i in range(4, n+1, 2):
    dp[i] = dp[i-2] * 3 + 2
    for j in range(4, i, 2):
        dp[i] += dp[i-j] * 2

print(dp[n])

 

좀 더 공부하자! ^^