[Algorithm] 2×n 타일링

[hwangJi-dev]

💬 문제

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

💬 Idea

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하자.

주어지는 직사각형의 너비 길이가 길어짐에 따라
이를 2x1, 1x2의 작은 단위 조합으로 쪼개어 본다면 규칙을 찾을 수 있다.

다음 그림을 보자.

기본적으로

2x1 크기의 직사각형은 2x1 타일 1개로만 채워질 수 있기에 1가지의 방법을 갖고

2x2 크기의 직사각형은 2x1 타일 2개 또는 1x2 타일 2개로 채워질 수 있기에 2가지의 방법을 갖는다.

다음으로 2x3 크기의 직사각형을 채우는 방법의 수를 알아보자.

2x3 크기의 직사각형을 2x1 과 1x2를 기준으로 쪼개어 본다면 아래 두 개의 조합이 나온다.

• 2x1 타일 1개 + 2x2 타일 1개
  • 2x2 타일을 채우는 방법의 수를 우리는 이전 단계에서 구해놓았으므로 2가지임을 알 수 있다.
  • 따라서 2x1 타일 1개와 2x2 타일 1개 조합으로 채울 수 있는 방법은 2가지 이다.
• 1x2 타일 2개 + 2x1 타일 1개
  • 2x1 타일을 채우는 방법의 수는 1가지이다.

따라서 두 개의 조합의 가지수를 더하면 2x3 크기의 직사각형을 채울 수 있는 방법의 수를 도출할 수 있다.

2x3 크기의 직사각형을 채울 수 있는 방법의 수: 2 + 1 = 3

다음으로 2x4 크기의 직사각형을 채우는 방법의 수를 알아보자.

2x4 크기의 직사각형을 2x1 과 1x2를 기준으로 쪼개어 본다면 아래 두 개의 조합이 나온다.

• 2x1 타일 1개 + 2x3 타일 1개
  • 2x3 타일을 채우는 방법의 수를 우리는 이전 단계에서 구해놓았으므로 3가지임을 알 수 있다.
  • 따라서 2x1 타일 1개 + 2x3 타일 1개 조합으로 채울 수 있는 방법은 3가지 이다.
• 1x2 타일 2개 + 2x2 타일 1개
  • 2x2 타일을 채우는 방법의 수를 우리는 이전 단계에서 구해놓았으므로 2가지임을 알 수 있다.
  • 따라서 2x1 타일 1개 + 2x2 타일 1개 조합으로 채울 수 있는 방법은 2가지 이다.

따라서 두 개의 조합의 가지수를 더하여 2x4 크기의 직사각형을 채울 수 있는 방법의 수를 도출할 수 있다.

2x4 크기의 직사각형을 채울 수 있는 방법의 수: 3 + 2 = 5

이렇게 직사각형을 쪼개어 생각해볼 수 있고 단계를 반복할 수록 아래와 같은 규칙을 따른다.

즉 2xn의 직사각형 을 1x2, 2x1의 타일로 채울 수 있는 방법의 수를 알기 위해서는
→ 이전 두개의 항 각각의 방법의 개수를 알고 있다면 해결할 수 있게 된다.

점화식으로 표현해본다면 아래와 같다.

💬 풀이

import Foundation

func solution11726() {
    let N = Int(readLine()!)!
    var rectangleArr = Array(repeating: 0, count: N + 1)
    
    if N == 1 {
        print(1)
    } else if N == 2 {
        print(2)
    } else {
        rectangleArr[1] = 1
        rectangleArr[2] = 2
        
        for i in 3...N {
            rectangleArr[i] = (rectangleArr[i - 1] + rectangleArr[i - 2]) % 10007
        }
        
        print(rectangleArr[N])
    }
}