[백준 2482] - 색상환(Kotlin)[골드3]

문제

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

2482번: 색상환

 

문제 풀이

이전의 선택한 색에 따라 다음 선택이 영향이 받는 문제였고, 배낭 문제와 굉장히 유사하게 느껴졌다.

배낭 문제와 같이 물건을 담으면서, 해당 물건을 담을 경우와 담지 않을 경우를 나눠서 계산하는 것처럼

해당 문제도 색깔을 선택할 경우와 선택하지 않을 경우를 나눠서 계산하는 문제였다.

 

우선 그림을 그려가면서 가장 먼저 발견한 조건은 k가 n의 절반보다 크다면 경우의 수는 0이라는 점이다.

이는 문제에서도 주어졌지만, 문제를 읽을 당시엔 이해를 하지 못했고, 실제로 그림을 그려가면서 이해할 수 있었다.

그림과 같이 색이 4개가 있을 때, k가 2일 경우는  (1,3) (2,4)를 선택할 수 있다.

하지만 k가 3개라면? 선택할 수 있는 경우의 수가 없다.

이와 같이 n개의 색 중에서 인접한 두 색을 고르지 않는 조건을 만족하면서 k개의 색을 고르는 경우는 없다.

즉 적어도 k는 n의 절반보다 크거나 같아야 함을 알 수 있다.

 

다음은 색을 선택해야 한다.

5를 선택했다면 선택할 수 있는 색깔의 범위는 3까지이다. 여기서 우리는 k-1개를 뽑아야 한다.

왜냐하면 5(1) + 1~3(k-1)를 합쳐 k개를 만들어야 하기 때문이다.

만약 5를 선택하지 않았다면 4번까지 선택할 수 있다.

따라서 우리는 1~4번의 범위에서 k개를 뽑아야 한다.

배낭과 유사하게 접근하는 것을 알 수 있다.

따라서 dp 점화식은 다음과 같다.

dp[i][j] = dp[i-1][j] + dp[i-2][j-1]

 

반복문의 범위에 대해서도 많은 고민을 했다.

우리는 위에서 n이라는 색깔의 범위 내에서 인접한 두 색을 선택하지 않으려고 할 때 n/2를 뽑을 수 없다는 것을 알고 있다.

저 그림에서도 6이라는 색을 선택할 때  최대 3개까지만 선택할 수 있음을 알 고 있다.

따라서 선택하려는 색(i)에 따라 j의 범위는 i/2가 최대임을 알 수 있다.

 

마지막으로 base case인 경우는 n개의 색 중에서 1개를 고르는 경우는 n개이기 때문에 해당 케이스는 따로 계산해 줬다.

 

전체 코드

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var k = 0
    private lateinit var dp: Array<IntArray>
    private val div = 1000000003

    fun run() {
        input()
        if (k > n / 2) {
            print(0)
            return
        }
        solve()
        print(dp[n][k])
    }

    private fun input() {
        n = br.readLine().toInt()
        k = br.readLine().toInt()
        dp = Array(n + 1) { IntArray(n + 1) }
    }

    private fun solve() {
        for (i in 0..n) {
            dp[i][1] = i
        }
        for (i in 1..n) {
            for (j in 2..i / 2) {
                dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % div
            }
        }
    }
}

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