[BOJ_2133_KOTLIN] 타일 채우기

 

문제

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

2133번: 타일 채우기

입력

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

출력

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

문제풀이

참고사이트

https://blog.naver.com/hands731/221806277981

2133번 : 타일 채우기

DP문제는 아직 너무 어려운 것 같다. 점화식을 찾으려고 나름대로 머리를 썼으나, 홀수인 경우 짝이 맞지않아 0이라는 것 그리고 N=2일 때, 3이 나오고 N=4일때 N=2인 부분이 2번 나와서 곱해진다는 것까지만 유추해낼 수 있었다. 도저히 풀리지가 않아 더보기 에서 나오는 참고 사이트를 진행하여 풀었다. DP 연습이 더 필요한 것 같다. 

 

소스코드

val N = readLine()!!.toInt()
val d = Array(1001) { 0 }

fun main() {
    // 홀수면 무조건 짝이 맞지 않아 0이다.
    if(N%2!=0) print(0)
    else print(dp(N))
}

fun dp(n: Int) :Int {
    if(n == 0) return 1
    if(n == 1) return 0
    if(n == 2) return 3
    if(d[n] != 0) return d[n]

    var res = 3 * dp(n-2)
    for (i in 3..n){
        if (i % 2 == 0) res += 2 * dp(n - i)
    }

    d[n] = res
    return d[n]
}