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

문제

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

2133번: 타일 채우기

 

문제 풀이

사실 대표적인 DP문제이다.

DP 문제는 차근차근 손으로 할 수 있는 만큼 해보는 것이 좋다고 생각한다.

 

n = 0인 경우

3*0의 크기의 벽을 채우는 경우의 수는 공집합이라는 느낌으로 1로 생각했다.

 

n = 1인 경우

 

3*1 크기의 벽은 주어진 도형을 통해서 채울 수 없다.

직접 그려보면 알 수 있다.

 

n = 2인 경우

3개의 모양으로  채울 수 있다.

 

n = 3인 경우

dp 문제이기 때문에 그 전에 구했던 도형들을 최대한 이용해보려고 했다.

3*3의 사각형인 경우 3*2 사각형과  3*1 사각형으로 분리할 수 있다.

하지만 어느 방법으로도 3*1의 남은 부분을 채우지 못한다.

 

슬슬 느낌이 왔는데 n이 홀수인 경우는 채울 수 있는 방법이 없는 것 같았다.

 

n = 4인 경우

 

3*4 사각형의 경우 3*2 사각형과 3*2 사각형, 3*2 사각형과 3*1 사각형 2개로 분리할 수 있다.

하지만 3*1 사각형을 채울 수 있는 방법은 없기 때문에 3*2 사각형 2개를 채울 수 있는 방법만 생각하면 된다.

처음은 단순하게 3*2 사각형을 채우는 방법이 3개니까 3*3을 하면 되지 않을까 생각했다.

하지만 테스트케이스의 그림을 보고 힌트를 얻었다.

마지막 부분을 보면 위에서 발견하지 못했던 모양을 발견할 수 있다.

길이가 4로 늘어난 만큼 새로운 모양이 생겼다. 위로 뒤집으면 하나 더 생기므로, 새로 생기는 문양 2개를 포함해서 11개를 만들 수 있다.

 

n = 5인 경우

홀수 이므로 0이다.

 

n = 6인 경우

 

이렇게 나뉠 수 있다.

생각해보면 3*4와 3*2 사각형을 채우는 방법을 2번 곱한 66이 될 것이라고 생각했다.

오른쪽의 3*4와 왼쪽의 3*4를 채우는 과정에서 중복이 발생할 수밖에 없다.

왜냐하면 3*4도 3*2 2개를 채우고 특정 모양 2개를 추가하기 때문이다. (실제로 그려보면 알 수 있다)

 

중복을 제거 하기 위해서는 왼쪽의 3*4와 오른쪽의 3*4를 다르게 채워야 한다.

그 다른 모양의 개수는 특이한 모양인 2개가 될 것이다.

 

따라서 11(3*4) * 3(3*2) + 2(특수문양) * 3 (3*2) = 39이다.

특수문양은 없을까 생각해 봤더니

3*4를 채우는 과정과 비슷하게 양 옆의 똑같은 패턴을 위치시키고, 가운데를 채우니까 아래 2가지 모양이 나왔다.

 

총 41개의 모양이 나왔다.

 

8개를 손으로 그리기에는 무리라서 여기서부터 점화식을 세워봤다.

dp [0] = 1, dp [2] = 3, dp [4] = 11, dp [6] = 41

 

dp [4]를 만들기 위해서 3*dp [2] + 2*dp [0]을 이용했다.

dp [6]의 점화식은 어떻게 세워야 할까

dp[6] = dp [4] * dp [2] + dp [2]* 2 + 2였다.

 

즉 점화식을 세워보면 dp [i] = dp [i-2] * dp [2] + dp [i-4]*2 + dp [i-6] * 2..... +dp [0]*2 임을 알 수 있다.

 

전체 코드

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private val dp = IntArray(31)
    fun run() {
        input()
        if (n % 2 == 0) {
            solve()
        }
        print(dp[n])
    }

    private fun input() {
        n = br.readLine().toInt()
    }

    private fun solve() {
        dp[0] = 1
        dp[2] = 3
        for (i in 4..n step 2) { // dp[i] = dp=
            dp[i] += 3*dp[i-2]
            for(j in  i-4 downTo  0 step 2){
                dp[i] += 2*dp[j]
            }
        }
    }
}

fun main() {
    val solution = Solution().run()
}