알고리즘

[백준] 11727 2 x n 타일링 2 - 실버 3

swanzzz 2025. 5. 12. 23:15
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • DP, 점화식, 구현

1. 문제설명

 

N이 최소 1부터 시작하는 2 x N 타일이 존재합니다.

 

이 타일을 채우는 경우의 수를 모두 구하고 그 수를 10,007로 나눠 출력하는 문제입니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 256MB
  • 1 ≤ n ≤ 1,000

2. 접근방식

DP 문제는 점화식을 얼마나 잘 세우느냐에 따라서 문제의 성공 여부가 달라집니다.

 

이번 문제는 2 x 1, 1 x 2, 2 x 2 타일로 2 x N 타일을 채우는 경우의 수를 구하는 문제 입니다.

 

N 이 1인 경우를 살펴보겠습니다.

 

2 x 1 타일을 채우는 경우의 수는 2 x 1 타일 1가지 뿐입니다.

 

N 이 2인 경우를 보겠습니다.

 

2 x 2 타일을 채우는 경우의 수는 2 x 1 을 2개, 1 x 2 타일을 2개, 2 x 2 타일을 1개 사용하는 3가지 경우가 존재합니다.

 

이제 N 이 3인 경우를 보겠습니다. 이해하기 쉽게 그림으로 그려 보았습니다.

 

 

기존의 2 x 2 타일을 채우는 방법들에 1 x 2 타일을 붙여 줍니다.

 

3칸을 채우는 경우의 수는 기존 2칸을 채우는 방식에 1 x 2 타일만 끼워주면 됩니다.

 

다른 방법으로는 1 x 2 타일에 2 x 1 타일 2개, 2 x 2 타일 1개를 각각 추가하는 방식 총 2가지가 존재합니다.

 

즉, 기존의 N 이 2인 경우의 수는 총 1번만 사용하였고

N 이 1인 경우의 수는 2번 사용하였습니다.

 

 

 

이렇게 그림으로 보면 좀더 이해가 쉬울 겁니다.

 

3칸을 채우는 경우를 만들기 위해서

 

2칸을 채우는 경우의 수를 1번 사용해 주었습니다.

 

1칸을 채우는 경우의 수는 2번 사용해 주었죠

 

이를 점화식으로 바꿔보면 DP[i] = DP[i - 1] + (DP[i - 2] * 2)

가 됩니다. 이를 코드로 구현해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

N = int(input())

# DP 배열 생성 후 초기값 설정
DP = [0] * (N + 1)
DP[0] = 1
DP[1] = 1

# 점화식 세우기
for i in range(2, N + 1):
    DP[i] = DP[i - 1] + (DP[i - 2] * 2)

# 출력
print(DP[N] % 10007)

[코드설명]

앞선 그림을 통해 세운 점화식을 코드로 옮겨 주었습니다.

 

한 가지 주의할 점은 N이 최소 1부터 최대 1,000 인 것 입니다.

 

N 이 최소 1부터 시작하는데 DP[1] = 1, DP[2] = 3 이런식으로 정의해버리면 인덱스 에러가 발생합니다.

4. 결과

[회고]

DP 문제는 점화식을 얼마나 잘 세우느냐가 관건인 문제 입니다.

 

이번 문제 역시 점화식을 세우기 위해 3을 뜯어보는 과정에서 처음에 모든 경우의 수를 그림으로 직접 그려보았습니다.

 

그렇게 하니까 생각보다 규칙을 찾기 어려웠습니다.

 

그래서 기존의 방식에 새로운 규칙을 추가하여 3칸을 채우는 경우는 뭐가 있는지 찾아 보았습니다.

 

기존의 2칸을 채우는 경우에 오른쪽에 1 x 2 타일을 추가하면 3칸을 채울 수 있었습니다.

 

또 기존의 1칸을 채우는 경우에 오른쪽에 2 x 1 타일과 2 x 2 타일을 채우는 방식으로 3칸을 채울 수 있었습니다.

 

최대한 기존의 방식을 활용하여 새로운 3칸을 채우는 경우의 수를 그리며 중복을 최대한 제거해주었고 점화식을 세울 수 있었습니다.

 

처음 indexError 도 문제의 제한사항에 N이 1부터 시작한다를 고려하지 않고 초기값 설정으로 DP[1]은 1 DP[2] = 3 이런식으로 초기값을 세웠는데 N이 1부터 시작하는 경우 DP[2] 에서 indexError 가 발생한 것이었습니다.

 

제한사항을 고려해 코드를 작성하였고 문제를 해결할 수 있었습니다.

 

다음시간에도 DP 문제를 풀어보며 DP 실력을 키워가 보겠습니다.

반응형