개발해요

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