개발해요

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

풀이

가장 먼저 시작되는 회의에 회의실을 배정한다. 그리고 현재 진행중인 회의들 중 가장 먼저 끝나는 회의와 다음에 시작할 회의의 시작 시간을 비교해서, 진행중인 회의의 끝나는 시간이 더 빠르다면 그 강의실에 새로 시작할 회의를 그대로 넣어준다. 반대로 새로 시작하는 시간이 더 빠르다면 새 회의실을 사용한다. 이렇게 하나씩 비교를 끝마치면, 남아있는 회의의 개수가 지금껏 사용한 회의실의 개수가 된다. 기존의 회의실만 삭제하는 경우는 없으며, 1:1로 교체하거나 추가로 생성만 하기 때문이다.

자료구조)

비교를 할 때 남아있는 회의들은 시작 시간순으로 접근하므로, 시작시간의 오름차순으로 정렬을 하고,

진행중인 회의들 중에서는 가장 빨리 끝나는 회의 하나만 꺼내서 비교하므로 끝나는 시간을 기준으로 우선순위 큐(최소힙)를 사용하면 편하게 구현할 수 있다.

우선순위 큐가 회의실이고, 회의=회의실로 생각해서 교체, 추가한다는 발상이 정말 인상적이었다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Meeting(val start: Int, val end: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val meetings = mutableListOf<Meeting>()
    val pq = PriorityQueue<Meeting>(compareBy{ it.end }) // 현재 진행중인 회의 저장(사용중인 회의실)

    repeat(n){
        val st = StringTokenizer(readLine())
        val meeting = Meeting(st.nextToken().toInt(), st.nextToken().toInt())
        meetings.add(meeting)
    }
    meetings.sortWith(compareBy{ it.start }) // 일찍 시작하는 순서대로 정렬

    pq.add(meetings[0])
    for (i in 1 until n){
        val prevMeeting = pq.peek()   // 진행중인 회의 중 가장 먼저 끝나는 회의
        val nextMeeting = meetings[i] // 다가올 회의 중 가장 먼저 시작하는 회의
        // 기존 회의가 먼저 끝나면 그 회의실에서 다음 회의를 진행할 수 있으므로, 기존 회의를 삭제한다
        if (prevMeeting.end <= nextMeeting.start){
            pq.poll()
        }

        pq.offer(nextMeeting)
    }

    // 회의를 1:1로 교체하거나 회의실이 부족하면 추가 회의실을 사용했기 때문에
    // 남아있는 회의의 개수 = 지금껏 사용한 회의실 개수
    println(pq.size)
}

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

코드

포도주 시식 문제(https://www.acmicpc.net/problem/2156)와 정말 비슷하다.

포도주 시식 포스팅: (https://best-human-developer.tistory.com/19)

다른 점이 하나 있는데, 포도주 문제에서는 i번째 포도주를 선택하지 않아도 되지만 계단 오르기에서는 i번째 계단을 반드시 밟아야 한다. i번째 계단을 밟지 않는 경우를 포함시키면 3칸 이상을 건너뛰는 상황이 발생해서, 한 번에 한 계단 또는 두 계단씩만 오를 수 있다는 조건1을 만족시키지 못하기 때문이다.

따라서,

함수) dp[i]: i번째 계단까지만 존재할 때, 조건1,2,3을 만족하는 최대 점수

점화식) i번째 계단 + i-1번째 계단을 밟는 경우와 i번째 계단 + i-2번째 계단을 밟는 경우 중 최대 값

-> dp[i] = max( stair[i] + stair[i-1] + dp[i-3] , stair[i] + dp[i-2] ) 

초기값) dp[0] = 1, dp[1] = stair[1], dp[2] = stair[1] + stair[2]

와 같이 반복문을 구성하면, 초기 값부터 조건을 만족하면서 모든 경우의 수를 포함하기 때문에 dp[3] ~ dp[n]까지 답을 구할 수 있다.

정답) dp[n]

풀이

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val stairs = IntArray(n+2)	// n+2: 초기 값 설정할 때 인덱스 에러를 막는다 
    val dp = IntArray(n+2)

    repeat(n) { i ->
        stairs[i+1] = readLine()!!.toInt()
    }

    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]
    for (i in 3..n){
        // 직전 계단+현재 계단, 두 칸 전 계단+현재 계단 중 최대 값
        // 현재 계단을 밟지 않는 경우도 포함시키면, 세 칸 이상을 뛰어넘는 경우가 발생한다
        dp[i] = max(stairs[i] + stairs[i-1] + dp[i-3], stairs[i] + dp[i-2])
    }

    println(dp[n])
}

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])
}