타일 채우기

이번주 내내 고민했던 문제였다. 블로그 풀이들을 봐도 이해가 잘 안됐었는데, 오늘 결국 이해를 해서 다른 블로그들 보다 조금 더 자세하게 설명해보려 한다.

그림을 통해 이해를 시도하기 전에 짚고 넘어가야할 부분이 몇가지 있다.

  1. 먼저, N X 3 크기의 벽에서 N이 홀수인 경우에는 2 X 1 타일 혹은 1 X 2 타일로 벽을 완전히 채울 수 없다. 타일의 넓이는 2로 짝수임으로 벽의 넓이도 짝수인 경우에만 벽을 완전히 채울 수 있다.

  2. 다음으로, 2 X 3크기의 벽을 채우는 경우의 수는 3가지이다. (그려보자)

  3. 마지막으로, N X 3(N%2==0) 크기의 벽에 타일을 배열할 때 1)세로로 나눌 수 없게 배치하는 경우의 수는 2)N에 상관 없이 2가지이다.

  • 1)세로로 나눌 수 없는 경우란?

Crepe

왼쪽의 경우 벽을 세로로 나눌 수 없게 배치한 경우이다. 오른쪽의 경우는 벽을 세로로 더 작게 나눌 수 있게 배치한 경우이다.

  • 2)N에 상관 없이 2가지?

Crepe

4와 6일 때, 위와 같이 더 작게 나눌 수 없는 경우의 수는 각각 2가지씩 이다. 4, 6, 8, 10, … 모두 2개씩 존재한다.

4 X 3 크기의 벽 까지는 손으로 그려서 확인해 볼 수도 있음으로 6부터 설명을 할 예정이다. 가로의 길이가 4인 벽을 채우는 경우의 수는 11이다.


6 X 3 크기의 벽을 채우는 경우의 수

Crepe

위의 그림에서 가로길이가 N인 ‘빨간색’ 박스는 가로 길이가 N보다 작은 박스들로 더이상 나눌 수 없는 박스를 의미한다.

세로 기준으로 나뉠 수 있는 경우들을 살펴보면 아래와 같이 4가지 경우가 나뉜다.

  • 2 X 3 크기의 벽 + 2 X 3 크기의 벽 + 2 X 3 크기의 벽으로 나눌 수 있는 경우
  • 4 X 3 크기의 벽 + 2 X 3 크기의 벽으로 나눌 수 있는 경우
  • 2 X 3 크기의 벽 + 4 X 3 크기의 벽으로 나눌 수 있는 경우
  • 세로로 나눌 수 없는 6 X 3 크기의 벽인 경우

이 네가지 경우를 왼쪽 ‘빨간색’ 박스 기준으로 조금 줄여보면 다시 세가지 경우로 나뉠 수 있다.

  • 빨간색 박스의 가로 길이가 2인 경우 » 2)에 의해서 가로길이가 2인 박스를 채우는 경우의 수는 3이다.
  • 빨간색 박스의 가로 길이가 4인 경우 » 3)에 의해서 가로길이가 4인 박스를 채우는 경우의 수는 2이다.
  • 빨간색 박스의 가로 길이가 6인 경우 » 3)에 의해서 가로길이가 6인 박스를 채우는 경우의 수는 2이다.

따라서 가로 길이가 6인 벽을 채우는 경우의 수는

  • 가로 길이가 4인 흰색 박스를 채우는 경우의 수 X 가로 길이가 2인 빨간색 박스를 채우는 경우의 수
  • 가로 길이가 2인 흰색 박스를 채우는 경우의 수 X 가로 길이가 4인 빨간색 박스를 채우는 경우의 수
  • 가로 길이가 6인 빨간색 박스를 채우는 경우의 수

를 모두 합한 값이다.

11×3 + 3×2 + 2 = 𝟒𝟏


8 X 3 크기의 벽을 채우는 경우의 수

Crepe

  • 빨간색 박스의 가로 길이가 2, 4, 6, 8 인 경우로 나눌 수 있다.

따라서 가로 길이가 8인 벽을 채우는 경우의 수는

  • 가로 길이가 6인 흰색 박스를 채우는 경우의 수 X 가로 길이가 2인 빨간색 박스를 채우는 경우의 수
  • 가로 길이가 4인 흰색 박스를 채우는 경우의 수 X 가로 길이가 4인 빨간색 박스를 채우는 경우의 수
  • 가로 길이가 2인 흰색 박스를 채우는 경우의 수 X 가로 길이가 6인 빨간색 박스를 채우는 경우의 수
  • 가로 길이가 8인 빨간색 박스를 채우는 경우의 수

를 모두 합한 값이다.

41×3 + (11+3)×2 + 2 = 𝟏𝟓𝟑


이를 토대로 dp 점화식을 세우면 아래와 같음을 알 수 있다!

  • n이 홀수인 경우는 모두 0임으로 홀수 경우를 모두 제외하고 N에 2를 나눈 값을 i에 대입했다.
𝑑𝑝[𝑖] = 𝑑𝑝[𝑖−1]×3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−1])×2 + 2
  • 위의 방법이 헷갈린다면, N을 2로 나누지 않고, 아래와 같은 점화식을 사용해도 무방하다.
if i%2==0:
    𝑑𝑝[𝑖] = 𝑑𝑝[𝑖−2]×3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−2])×2 + 2
else:
    dp[i] = 0
  • 함께 공부하는 분이 알려주신 더 간단한 점화식도 살펴보자.
𝑑𝑝[𝑖]

= 𝑑𝑝[𝑖−1]×3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−1])×2 + 2

=  𝑑𝑝[𝑖−1]×3 + dp[i-2]x2 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−2])×2 + 2

=  𝑑𝑝[𝑖−1]×3 + dp[i-2]x3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−2])×2 + 2 - dp[i-2]

=  𝑑𝑝[𝑖−1]×3 + dp[i-1] - dp[i-2]
   (dp[i-1] = dp[i-2]x3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−2])×2 + 2)

=  𝑑𝑝[𝑖−1]×4 - dp[i-2]


구현

위의 점화식에서 sum을 통해 dp[0] 부터 dp[i-2]까지 더하는 부분을 매번 해줘도 되지만, 시간복잡도를 줄이기 위해서 dp[i]에 sum(dp[:i+1])값도 저장하며 진행했다.

#벽을 채우는 경우의 수 저장
𝑑𝑝[𝑖] = 𝑑𝑝[𝑖−1]×3 + 𝑠𝑢𝑚(𝑑𝑝[:𝑖−1])×2 + 2
#sum(dp[:i+1])값 저장
dp[i][1] = dp[i][0] + dp[i-1][1]


CODE

import sys
read = sys.stdin.readline

n = int(read())
# n이 홀수일 경우 벽을 채울 수 있는 방법이 없다.
if n % 2 == 1:
    print(0)
    sys.exit()
# 첫 번째 값에는 벽을 채울 수 있는 경우의 수,
# 두 번째 값에는 dp 첫 번째 값들의 총 합을 저장한다.
dp = list([0, 0] for _ in range(n//2+1))
dp[1] = [3, 3]

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

print(dp[-1][0])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]