개발해요

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

풀이

어떤 방법을 써야 할까?

1 <= n <= 100,000이므로 모든 경우를 탐색해보면 시간초과가 나고, 정렬을 해서 푸는 문제도 아닌 듯 하다. 따라서, 이분 탐색을 사용하는 문제는 아니고, 그리디한 방법도 떠오르진 않는다.

접근 방법에 대해 생각해봤는데, 사실 이 문제는 다이나믹 프로그래밍을 사용하는 것으로 유명한 문제 중 하나이다.

나는 다이나믹 프로그래밍 문제를 다음과 같은 절차로 풀려고 한다.

1. 반복문에서 사용할 점화식을 찾기 위해 함수를 정의한다. 

-> dp[i]: 배열이 i번째 까지만 있을 때, 시작 위치가 어디든 number[i]로 끝나는 최대 연속합 (number[?] ~ number[i])

ex) 2, 1, -4, 3, 4, -4, 6, 5, -5, 1 -> dp[2] = -1, dp[3] = 3

2. 문제에 따라서 아무것도 없는 상태(ex: 0) or 첫 인덱스의 값을 초기 값으로 설정한다.

-> dp[0] = number[0]

3. (2.)를 고려해서, 모든 경우의 수를 커버할 수 있는 점화식을 찾는다. 

-> dp[i] = {

                if (dp[i-1] < 0) number[i] 

                else) dp[i-1] + number[i]

              }

             < == > max( dp[i - 1] + number[i] , number[i] ) 

(수학적 귀납법과 같다!)

음수가 키포인트이지만, number[i]가 아니라 dp[i-1]이 음수인지의 여부가 중요하다. number[i]가 음수일지라도 dp[i-1]이 양수이면 dp[i] = dp[i-1] + number[i]이어야 한다. 그래야 1, -4, 3, 4, -4, 6, 5, -5, 1에서 3, 4, -4, 6, 5를 찾아낼 수 있다. 반면에 number[i]가 무슨 값이든 dp[i-1]이 음수이면, dp[i] = number[i]이다. 위 예시의 dp[3]에서 확인할 수 있다.

그리고 함수의 정의에 의해, dp 값들 중 최대 값이 답이 된다.

함수랑 점화식을 어떻게 잘 정의할 수 있을까?

경험의 영역인 것 같다. 나는 처음에 정말 모르겠어서 머리 깨져가면서 여러 문제 풀고, 이해하고, 다른 사람들 코드도 보니까 조금 익숙해졌다. dp는 몰아서 푸는 게 도움되는 것 같다.

코드

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val number = readLine()!!.trim().split(" ").map { it.toInt() }
    val dp = IntArray(n) { i -> number[i] }

    var answer = number[0]
    for (i in 1 until n) {
        if (dp[i - 1] < 0) dp[i] = number[i]
        else dp[i] = dp[i - 1] + number[i]
        // dp[i] = max(number[i], dp[i - 1] + number[i])와 같음
        
        answer = max(answer, dp[i])

        /* 틀렸던 코드
        if (0 <= number[i]){
            dp[i] = max(dp[i], dp[i-1] + number[i])
            answer = max(answer, dp[i])
        }
        */
    }

    println(answer)
}

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

풀이

1 <= n <= 10,000이라서 모두 탐색하면 시간 초과가 난다. 풀어보면 어떻게 과거의 모든 경우의 수를 예측해서 문제를 해결하지 싶은데, 이런 경우에는 다이나믹 프로그래밍을 사용할 때가 많았다.

나는 다이나믹 프로그래밍 문제를 다음과 같은 절차로 해결한다.

1. 반복문에서 사용할 점화식을 구성하기 위해 함수를 정의한다.

-> dp[i]: 포도주가 i번째 까지 있을 때, 조건을 만족하는 최대 포도주 양

2. 함수의 초기 값을 설정한다.

-> dp[0] = 0, dp[1] = wine[1], dp[2] = wine[1] + wine[2] (포도주 인덱스는 1부터 시작하도록 세팅)

3. 초기 값을 기반으로 모든 경우의 수를 커버할 수 있는 점화식을 구한다.

-> dp[i] =

{

 if (i번째 와인을 마시지 않는다) dp[i-1] 

 if (i번째, i-1번째 와인을 마시고, i-2는 마시지 않는다) wine[i] + wine[i-1] + dp[i-3] 

 if (i번째, i-2번째 와인을 마시고, i-1은 마시지 않는다) wine[i] + dp[i-2]

}

이렇게 반드시 조건을 만족시키게 점화식을 구성하고, 초기 값부터 점화식을 만족하도록 설정하면 모든 항이 조건을 만족하게 된다.

그리고 점화식을 구성하면서 i-3까지 인덱스를 봐야 하길래, 3번째 포도주부터 반복문을 돌리기 위해 포도주 인덱스를 1부터 시작했다. 

그리고 i를 3 ~ n까지 반복문을 돌려서 dp 값을 구하면, dp[n]이 답이 된다.

코드

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val wines = IntArray(n+2)
    val dp = IntArray(n+2)
    
    // 포도주 인덱스 1부터 시작
    repeat(n){ i ->
        wines[i+1] = readLine()!!.toInt()
    }

    // 초기값 설정
    dp[1] = wines[1]
    dp[2] = wines[1] + wines[2]
    for (i in 3..n){
        // 점화식
        val maxWithCurrentWine 
            = max(dp[i-3] + wines[i-1] + wines[i], dp[i-2] + wines[i]) // i번째 와인을 마시는 경우 중 최대 값 
        dp[i] 
            = max(dp[i-1], maxWithCurrentWine) // i번째 와인을 마시는 or 안마시는 경우 중 최대 값
    }

    println(dp[n])
}

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

풀이

문제가 실버라서 얕봤다가 크게 다쳤다. 조건 자체를 이해하기 어려웠는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하라는 말이 와닿지 않았다. 가장 인접한, 최대 거리??

그래서 마이구미님 블로그(https://mygumi.tistory.com/301)를 참고해서 이해할 수 있었다.

위 말을 맥락적으로 해석하면, 최대한 공평하면서도 간격이 크게 공유기를 설치하라는 것이다. 특정 두 집의 사이의 설치 간격이 너무 커지면, 그만큼 나머지 설치된 집들 사이의 간격은 짧아져서 가장 인접한 설치 거리가 짧아지기 때문이다.

즉, 거리가 가장 가까운 두 공유기 사이의 거리를 k라고 하면, 나머지 인접한 공유기들 사이의 모두 k보다 크거나 같아야 한다.

ex) k = 3,  2 <-> 5 <-> 12 <-> 15 <-> 19  - (공유기가 설치된 위치)

                         3        7           3           4          - (사이 거리) --> 모두 3보다 크거나 같다

이 문제는 이분 탐색의 응용인 파라메트릭 서치를 통해서 해결하는 문제로 알려져 있는데, 방법은 다음과 같다.

1. 가장 인접한 공유기 사이의 거리를 대상으로 이분탐색을 진행한한다.

2. 그 거리보다 크거나 같도록하는 기준을 만족시키면서 왼쪽 집부터 공유기를 설치하면서 갯수를 센다. 

3. 문제에서 주어진 공유기의 개수와 설치한 공유기의 개수를 비교해서, 같거나 더 많이 설치했다면 간격을 늘리고, 더 적게 설치했다면 간격을 줄인다.

4. left(lower) <= right(upper)일 때까지 1~3번을 반복하여 가장 인접한 설치 거리의 상한선을 찾는다.   

여기서 이해가 안갔던 건 왜 왼쪽 집부터 항상 공유기를 설치하느냐는 것이었다. 정확하게 증명하려면 약간의 수학이 필요한듯 한데, 자세한 건 https://www.acmicpc.net/board/view/50802를 참고해보자.

코드

fun main(){
    var n = 0
    var c = 0
    val listOfHouse = mutableListOf<Int>()

    readLine()!!.trim().split(" ").map{ it.toInt() }.let{
        n = it[0]
        c = it[1]
    }

    repeat(n){
        listOfHouse.add(readLine()!!.toInt())
    }
    listOfHouse.sort()	// 정렬: 이분탐색의 전제 조건

    var lower = 1	// 최소 간격
    var upper = listOfHouse.last() - listOfHouse[0]	// 최대 간격: 양 끝 집 사이의 거리
    var answer = upper

    while(lower <= upper){
        val mid = (lower + upper) / 2
        var count = 1			// 공유기 설치한 횟수
        var prevHouseIdx = 0	// 직전에 설치된 집

        // mid보다 인접 간격이 길거나 같도록 설치한다
        for(i in 1 until n){
            if (listOfHouse[i] - listOfHouse[prevHouseIdx] >= mid){
                count++
                prevHouseIdx = i
            }
        }
        
        // c == count -> 간격을 더 늘려도 모두 설치할 수 있는지 확인해본다
        // c < count -> 더 많이 설치됐다 -> 설치 간격을 늘려본다
        if (c <= count){
            lower = mid + 1
            answer = mid
        }else{			// 더 많은 공유기를 설치해야 한다 -> 간격을 줄인다
            upper = mid - 1
        }
    }

    println(answer)
}