[백준알고리즘] 2133번: 타일 채우기 -Python

[백준알고리즘] 2133번: 타일 채우기 -Python

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

2133번: 타일 채우기

이번 문제는 집중력이 부족하기도 했고 어렵기도 했다. ㅠㅠㅠㅠㅠ

다 풀고 보니까 너무 간단해보이는데...

 

우선은 짝수일 때만 채울 수 있다. 홀수에서는 채울 수 있는 방법이 없고, 무조건 0을 출력하게 된다.

그리고 2칸일 때는 3가지의 경우가 존재한다.

여기까지는 너무 간단했다.. 규칙찾고 점화식 만드는 데 오래걸렸다.

 

짝수일때만 경우의 수를 구할 수 있기 때문에 계산식을 세울 수 있다.

3x4라고 할 경우에는 3x2 두 개를 이용하거나 3x4를 이용할 수 있다. 가로가 2인 타일묶음을 두 개 사용하는 경우의 수는 9개이다. 여기서 가로가 4인 타일묶음을 한 개 사용하는 경우에는 2개가 존재하게 된다. 가로가 4인 타일묶음이 2가지 경우가 존재하는 이유는 아래의 사진과 같이 가능하기 때문이다.

저런 식의 타일묶음은 가로가 4뿐만아니라 6, 8, 10... 모두 두개씩 존재하게 된다는 것을 알게 된다.

 

다시 돌아와서 그렇다면 가로가 3x4를 채우기 위한 경우의 수는 어떻게 구할 수 있는지 생각해보아야 한다.

1. 가로가 2인 타일묶음 두 개를 사용

  가로가 2인 타일묶음의 경우의 수는 3개이기 때문에 3x3의 경우의 수가 존재

2. 가로가 4인 타일묶음 한 개를 사용

  가로가 4인 타일묶음의 경우의 수는 2개이기 때문에 2의 경우의 수가 존재

-> 3*3 + 2 = 11

 

그런데 여기서  가로가 2인 타일묶음을 두 개 사용하는 것은 가로가 2인 타일묶음에 가로가 2인 타일묶음을 추가하는 것과 같다. 가로가 4인 타일묶음을 한 개 사용하는 것은 가로가 0인 타일묶음에 가로가 4인 타일묶음을 추가하는 것과 같다. 하지만 아직 여기서는 이해가 잘 안 될 것이다.

 

여기서 그럼 3x6을 채운다고 생각해보자. 가장 먼저 가로가 6인 타일 묶음이 2개 존재할 수 있다는 것은 알 수 있다. 그렇다면 나머지를 채우는 것이 문제인데, 다음과 같이 생각해 볼 수 있다. 여기서는 타일묶음을 추가하는 개념으로 설명했다.

1. 가로가 4인 타일묶음 한 개에 가로가 2인 타일묶음 한 개 추가

  가로가 4인 타일묶음의 경우의 수는 위에서 11로 구했다. 여기서 추가할 가로가 2인 타일묶음의 경우의 수는 3이다.

2. 가로가 2인 타일묶음 한 개에 가로가 4인 타일묶음 한 개 추가

  가로가 2인 타일묶음의 경우의 수는 처음에 3인 것을 확인했다. 여기서 추가할 가로가 4인 타일묶음의 수는 가로가 2인 타일묶음 두 개로 나눌 수 없는, 위의 그림과 같은 모양의 타일묶음으로, 2개 존재할 수 있다.

3. 가로가 0인 타일묶음 한 개에 가로가 6인 타일묶음 한 개 추가

  가로가 0인 타일묶음의 경우의 수는 0이다. 나눌 수 없는 가로가 6인 타일묶음의 수는 가로가 4인 타일묶음과 같이 2개이다.

-> 11*3 + 3*2 + 2 = 41

 

즉, 나눌 수 없는 가로가 2인 타일묶음을 추가하는 경우의는 3을 곱해주고, 나눌 수 없는 가로가 4, 6, 8...인 타일묶음을 추가하는 경우의는 2를 곱해주면 된다. 이것을 알아내는데 오래걸렸다.

 

참고했던 반례다.

input : 8 -> output : 153

input : 12 -> output : 2131

 

import sys

N = int(sys.stdin.readline())
cases = [0] * 31
cases[2] = 3

for i in range(4, N+1, 2):
    cases[i] = 2 + cases[i-2] * 3 + sum(cases[:i-2]) * 2

sys.stdout.write(str(cases[N]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다