[백준] 2133 타일 채우기

알고리즘

[백준] 2133 타일 채우기 - 골드 4

swanzzz 2025. 5. 29. 21:22

[오늘의 문제]

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

[오늘의 학습 키워드]

DP
구현

1. 문제설명

3 x N 크기의 벽을 2x1 타일과 1x2 타일로 채우는 경우의 수를 구하는 문제 입니다.

타일의 세로 크기가 3으로 고정되어 있고 주어진 타일은 모두 2크기의 타일이므로 N이 홀수가 될 때는 타일을 제대로 채울 수 없습니다.

[제한사항]

시간 제한 2초
메모리 제한 128MB
1 ≤ N ≤ 30

2. 접근방식

문제를 해결하기 위해 우선 힌트를 살펴 보았습니다.

위 그림은 3 x 12 크기의 벽을 채우는 경우의 수 중 1개를 예시로 보여준 그림 입니다.

여기서 생각해 볼 수 있는 것은

1. 짝수마다 타일을 채울 수 있다.

2. 기본적으로 반복되는 기본 모양이 존재한다.

3. 규칙을 깨는 특수 모양이 존재한다.

입니다.

우선 기본 모양을 살펴보죠

N이 짝수일 때만 타일을 채울 수 있으므로 기본 모양은 다음과 같이 생성될 것입니다.

위 3가지 모양이 존재하는데

N이 2인 경우 위 3가지 조건밖에 없습니다.

N이 4인 경우 위 3가지 경우를 조합하여 총 9가지의 모양을 만들 수 있죠

이렇게 위 3가지 모양을 조합 및 반복을 통해 9가지의 모양이 생성되고 규칙이 존재합니다.

여기서 규칙을 깨는 모양이 2가지 존재합니다.

위 그림은 N이 4일때 규칙을 깨는 모양입니다.

이렇게 모든 조건을 확인하면 N이 4일때 최종 경우의 수는 11가지가 존재하게 되죠

이제 N이 6일때를 살펴 보겠습니다.

기본적으로 앞서 3가지 기본모양을 조합해서 9가지의 경우의 수를 생성하였는데

이 9가지의 경우의 수에 각각 3가지 기본 모양을 다시 추가하여 총 27개의 기본 모양을 생성할 수 있습니다.

그림으로 그려보면 이런 모양이 되겠죠

여기에 앞서 발견한 규칙을 깨는 모양 2가지에 기본 모양 3가지를 추가하여 12개의 새로운 모양을 생성할 수 있습니다.

이 모양의 앞 혹은 뒤에 기본 모양 3가지를 추가한다면 총 12개의 새로운 모양을 생성할 수 있죠

또 규칙이 깨지는 모양 2가지가 존재합니다.

앞서 발견한 규칙이 깨지는 모양이 늘어난 모양이죠

이 모양까지 추가하면 총 14개의 규칙이 깨지는 모양이 생성되고 모두 더하면 41가지의 경우의 수가 생성되죠

이러면 N이 6일때 경우의 수들을 나열해 보면 [0, 3, 0, 11, 0, 41] 이렇게 생성되죠

여기서 규칙을 찾을 수 있습니다.

41을 만들기 위해서는 11을 4번 곱하고 3을 빼줘야 41이 되죠

동일하게 11을 만들기 위해서는 3을 4번 곱하고 1을 빼줘야 합니다.

여기서 규칙이 보이는데 41을 만들기 위해 값이 존재하는 41의 두번째 전 값을 4번 곱해주고 4번째 전 값을 빼줬습니다.

동일하게 11을 만들기 위해서 11의 두번째 전 값을 4번 곱해주고 4번째 전 값을 빼주면 되겠죠

그러면 DP 테이블을 생성하고 초기화 할때 DP[0] 을 1로 초기화 하면 규칙이 맞게 생성되겠죠

이 규칙대로 N이 8일때를 생각해보면

41을 4번 곱하고 11을 빼줘야하죠 이러면 164 - 11 로 153 됩니다.

찾아낸 점화식을 토대로 코드로 작성해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
DP = [0] * (N + 2)  # N이 1부터 주어지는데 2는 3으로 초기화 시켜야 올바르게 규칙을 맞추기 때문에 N + 2 까지 생성

# DP 테이블 초기화
DP[0] = 1
DP[2] = 3

# 점화식을 토대로 값 채우기
for i in range(3, N + 1):
    
    # 홀 수는 건너 뛰고 짝 수만 채워주기
    if i % 2 == 1:
        continue
    else:
        DP[i] = DP[i - 2] * 4 - DP[i - 4]

print(DP[N])

[코드설명]

입력을 받고 DP 테이블을 생성해주는데

제한사항에 N이 1부터 30까지 주어진다고 되어 있습니다.

그러나 코드가 제대로 동작하려면 DP의 2번 테이블까지 초기화 되어 있어야 합니다.

파이썬의 특성상 리스트의 index가 0번 이하로 내려가는 경우 리스트의 마지막 index로 이동하게 되는데

이러면 N의 계산이 틀려지기 때문에 계산을 맞춰주기 위해서 DP 테이블을 N + 2로 생성해 주었고,

N이 1이 주어지더라도 DP[2]를 초기화 할 수 있기 때문에 반복문은 3부터 실행해 주었습니다.

홀 수 크기는 타일을 채울 수 없기 때문에 홀 수는 건너뛰고 짝수만 점화식을 토대로 값을 채워주고 결과를 출력해 주었습니다.

4. 결과

[회고]

이번 문제는 푸는데 시간이 조금 오래 걸렸습니다.

그 이유가 처음 점화식을 잘못 세웠기 때문인데 저는 이번 문제를 해결하는 핵심 방법은 기본 모양 3가지와 규칙이 깨지는 모양 2가지를 이용하는 방법 이었습니다.

N이 4가 주어질 때 기본모양 3개를 조합한 9개의 모양이 생성되고 규칙이 깨지는 모양 2가지가 존재합니다.

N이 6이 주어진다면 그 9개의 모양에 새로이 3개의 모양을 각각 앞뒤로 추가하는 방식으로 총 27개의 모양이 생성되고

규칙이 깨지는 모양 역시 2개의 모양에 기본 모양 3개를 앞뒤로 추가하는 방식으로 12개를 생성하였습니다.

또 규칙이 깨지는 모양 2가지가 추가로 존재하는데 여기까지 생각하지 못하고 27 + 12를 했는데 41로 계산해 버렸습니다.

우연찮게 N이 6일때의 값을 맞춰서 이 값을 이용해 점화식을 세우기 시작했고 제가 처음 세웠던 점화식은 다음과 같습니다.

import sys
input = sys.stdin.readline

N = int(input())
DP = [0] * 31
DP[0] = 1
DP[2] = 3
i = 2
j = 0

for num in range(4, 31):
    if num % 2 == 1:
        continue
    else:
        DP[num] = 3 ** i + (2 * (6 ** j))
        i += 1
        j += 1

print(DP[N])

이 코드가 정말 웃겼던게 이렇게 세운 값이 N이 8인 경우를 맞춰서 더 확신을 세웠던것 같습니다.

오류로 착각한 값이 우연히 41이였고 N이 8 주어진 경우의 수는 153가지가 존재하는데 이 코드로 8을 돌리면 153이 나왔습니다.

또 N 이 2가 주어진 경우 11이 나와야 하는데 6^0 의 결과값이 1이고 이 값에 2를 곱하니 11까지 입력이 되었죠

그래서 틀렸고 오류를 찾는 과정이 오래 걸렸습니다.

excel로 N이 6이 주어졌을때의 모든 경우의 수를 그려보았고

제 생각대로 작성한 경우의 수는 여기까지 였는데 저는 41을 생각했던 것입니다. 위 그림은 39가지의 경우의 수만을 보여주고 있었고 제가 2가지 경우를 빠트린것을 깨닫고 어떤 경우인지 찾던 와중

이 모양을 찾았던 것이죠....

그래서 전반적으로 코드를 수정하였고 점화식을 다시 세웠습니다.

제가 세운 점화식은 너무 복잡했고 8 이상은 모조리 틀리기 때문에 정확한 점화식을 다시 세웠어야 합니다.

기본 모양이 3제곱씩 반복되는 것은 알겠는데 규칙이 깨진 새로운 모양의 발생이 일정치 않았고 제대로 값을 계산하기 위해서는 다른 방법이 필요했죠

따라서 점화식의 본질대로 숫자에 집중했고 41을 주어진 숫자로 만드는 모든 경우의 수를 계산해 보았습니다.

그러다 11 x 4 -3 을 찾았고 이 값이 그대로 11에도 적용되기 위해선 0이 1로 초기화 될 필요가 있었죠

이를 통해 문제를 해결할 수 있었습니다.

오래 걸렸지만 포기하지 않고 스스로 점화식을 찾았고 결국 정답을 맞춰 더욱 인상깊은 문제였던것 같습니다.