DP : 타일 채우기 [백준 2133, Kotlin]

[문제]

문제

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

입력

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

출력

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

힌트

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

[풀이]

n = 2

3

 

n = 4

3 * 3 + 2 =11

 

n = 6

11 * 3 + 2 * 3 + 2 = 41 

 

n = 8

41 * 3 + 2 * 11 + 2 * 3 + 2 = 123 + 22 + 6 + 2 = 153

 

즉

 

A[2n] = 3 * [2n-2] + [2n-2] - [2n-4] -> A[2n] = 4A[2n-2] - A[2n-4]

 

dp array 크기를 최대로 해도 되지만 메모리 절약을 위해

1과 3은 0으로 return

2는 3으로 return

 

n> 4 이상이면

2개씩 증가하면서 짝수만 값 갱신

 

[코드]

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    if (n == 1 || n == 3) {
        println(0)
        return
    }

    if (n == 2) {
        println(3)
        return
    }

    val dp = IntArray(n + 1) { 0 }
    dp[0] = 1
    dp[2] = 3

    for (i in 4..n step (2)) {
        dp[i] = 4 * dp[i - 2] - dp[i - 4]
    }
    println(dp[n])
}

[출처]

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

2133번: 타일 채우기