[백준/BOJ] 11726번: 2×n 타일링

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

11726번: 2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

해설

dp를 사용하여 문제를 풀었다.

우선 n에 따른 경우의 수를 보자.

• n = 1일 경우 경우의 수는 (l) 하나이다.
• n = 2라 하면 (ll, =)로 2가지 경우가 있다.
• n = 3일 경우 (lll, l=, =l) 3가지 경우가 있다.
• n = 4라면, (llll, =ll, l=l, ll=, ==) 5가지 경우가 있다.

n=4일 때 경우의 수들을 보자.

llll, =ll, 1=1는 n=3일 때의 경우의 수들에 오른쪽 끝에 l(1*2타일)을 추가한 것과 같다.

또한 ll=, ==는 n=2일 떄의 경우의 수들의 끝에 =(2*2타일)을 추가한 것과 같다.

따라서 dp[n] = dp[n-1] + dp[n-2]라 두고 이 값에 % 10007를 한 값을 출력하면 된다.

소스 코드

fun main() {
    val n = readLine()!!.toInt()
    val dp = Array(1001) { 0 }
    dp[1] = 1
    dp[2] = 2
    for(i in 3 .. n) dp[i] = (dp[i-1] + dp[i-2]) % 10007
    println(dp[n])
}