타일 채우기

타일 채우기

문제

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

문제 해석

dp를 이용하는 문제이다. 일정 규칙을 찾아 점화식을 세운 후 dp를 이용하여 풀면 쉽게 풀리지만, 규칙을 찾기에 매우 어려운 문제이다.

풀이

[그림 1]

N 값이 홀수일 때

• [그림 1]과 같이 벽을 채우지 못한다. 홀수는 짝수로 나누어지지 않기 때문에 분명히 빈 곳이 생기게 된다.

[그림 2]

N = 2 일 때

• [그림 2]와 같이 3가지 경우의 수가 존재한다.

[그림 3]

N = 4 일 때

• [그림 2]에서 구한 것 처럼 N = 2 일 때 그림 2개를 합친 것이 N = 4 이다.
• 그렇다면 N = 4 일 때의 경우의 수는 3 * 3 = 9 인가?
• 아니다. [그림 3]에서 보이는 것처럼 고유 모양 2가지의 경우의 수가 추가된다.
• 그렇다면 3 * 3 + 2 = 11이다.

[그림 4]

N 일 때

• N으로 정해놓고 그림을 보면 [그림 4]처럼 N - 2와 N = 2 일 때로 나눌 수 있다.
• 그렇다면 점화식은 dp[N] = dp[N - 2] * 3 + 2인가?
• 아니다. N >= 4라면 [그림 3]처럼 그림이 2개씩 더 생기는 경우도 생각을 해야한다.
• N - 4, N = 4 일 때로 나누었을 때, N - 6, N = 6 일 때, N - 8, N = 8 일 때 ......
• 이렇게 쭉 나누어서 봐야 한다.
• 그렇다면 dp[N] = dp[N - 2] 3 + dp[N - 4] 2 + dp[N - 6] * 2 + .... + 2이다.
• 왜 고유 모양 2개만 생각을 하고 dp[N - 4], dp[N - 6]의 경우는 생각을 안하냐고 생각할 수 있다.
• 이유는 각 (dp[N - 4], dp[4]), (dp[N - 6], dp[6])...은 따로 분리해서 본 것이다. 따로 분리해서 본 것은 (dp[N - 2], dp[2])에서 이미 고려를 하였다. 합쳐서 본 것이 아닌 따로 분리해서 본 것이기 때문에 모양이 다 포함이 되어 있다. 그래서 우리는 각 고유 모양들만 생각을 하면 된다.
• 점화식 : dp[N] = dp[N - 2] dp[2] + (dp[N - 4] 2(고유 모양) + dp[N - 6] * 2(고유 모양) + ....) + 2(고유 모양)이다.

import sys

N = int(sys.stdin.readline())

dp = [0] * (N + 1)

if N % 2 != 0:
    print("0")
else:
    dp[0] = 1
    dp[2] = 3
    for i in range(4, N + 1, 2):
        dp[i] = dp[i - 2] * 3 + sum(dp[2:(i - 2)]) * 2 + 2
    print(dp[N])   

고찰

• 솔직히 말해서 혼자 스스로 규칙을 찾아서 푼 문제가 아니다.
• 엄청나게 많이 고민을 해봤고, dfs를 사용해서 코딩을 해볼까도 생각을 하였다.
• 하지만 코드 자체가 너무 방대해지고 재귀 호출을 너무 많이 하였다.
• dp를 이용해서 푸는 것은 알고 있었지만, 규칙을 찾기가 너무 어려웠다.
• 다른 사람들이 푼 풀이를 보고 이해하는데도 시간이 많이 갔다.