개발해요

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

풀이

이전 항으로 다음 항의 값을 구할 수 있는 다이나믹 프로그래밍 문제이다.

문제의 상황을 수식으로 나타내보면 다음과 같다.

이렇게 되는 경우의 수를 dp[k][N]이라고 할 떄, 위에 수식은 아래처럼 다시 바꿔서 표현할 수 있다.

L이라는 값을 미리 더해서 (0 ~ n-L)까지 k-1개의 숫자를 더해서 N-L을 만드는 경우의 수를 구하는 상황으로 바꿀 수 있고, k-1개로 묶인 부분이 dp[k-1][N-L]이 된다.

그러면 dp[k][N] = sum( dp[k-1][N-L] ) (0 <= L <= N)이라는 점화식을 만들어낼 수 있는데, 변수가 3개이므로 3중 반복문을 사용해서 구현할 수 있다.

dp[k][N]의 식을 조금 살펴보면,

k = 1일 때 즉, 숫자 하나로 N을 만드는 경우의 수는 N이 무엇이든 항상 N 하나이므로 dp[1][N] = 1이다. 그리고 이게 초기 값이 된다.

n =0일 때는 숫자가 몇 개든지 0만 더해지는 경우밖에 없다. 따라서 dp[k][0] = 1이다. 

ex) dp[4][0] = 1 (0 + 0 + 0 +0)

그리고 이것들이 dp의 초기 값이 된다.

머리로만 하면 이해가 잘 안될 수도 있어서 직접 해보는 게 좋다. 내가 그랬다ㅋ_ㅋ

ex) n = 6, k = 4일 때 반복문 결과

계산하다 보면 dp[k][n] = dp[k][n-1] + dp[k-1][n] 이라는 특이한 구조를 발견할 수 있다. 이 점화식을 사용하면 변수가 두 개라서 이중반복문으로 좀 더 빠르게 구현이 가능하다!

삼중반복문이 처음엔 머리에 잘 안들어왔었는데, 직접 해보는게 이해에 도움이 많이 됐던 문제다.

코드1 (삼중 반복문)

fun main(){
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    val dp = Array(k+1){IntArray(n+1)}

    for (i in 0..n) dp[1][i] = 1

    for (i in 2..k){		// 행: 더하는 숫자 개수
        for (j in 0..n){	// 열: 더해서 나와야 하는 값
            for (m in 0..j){
                dp[i][j] += dp[i-1][j - m] // 직전 행의 처음~현재 열까지 더한다.
                dp[i][j] %= 1_000_000_000
            }
        }
    }
    
    println(dp[k][n])
}

코드2 (재귀)

lateinit var dp: Array<IntArray>

fun main() {
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    dp = Array(k+1){IntArray(n+1)}

    for (i in 0..n){
        dp[1][i] = 1	// 더하는 숫자가 하나일 때
    }

    println(findAnswer(n, k))
}

private fun findAnswer(n: Int, k:Int): Int {
    if (dp[k][n] != 0) return dp[k][n]

    for (i in 0..n){
        dp[k][n] += findAnswer(n-i, k-1)
        dp[k][n] %= 1_000_000_000
    }

    return dp[k][n]
}

코드3 (이중 반복문)

fun main(){
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    val dp = Array(k+1){IntArray(n+1)}

    for (i in 1..k) dp[i][0] = 1 // 합한 값이 0인 경우는 항상 한 가지이다
    for (i in 1..n) dp[0][i] = 0 // dp[1][i] = 1로 세팅하고, 반복문을 2..k으로 시작하는 거랑 같음 

    for (i in 1..k){
        for (j in 1..n){
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= 1_000_000_000
        }
    }

    println(dp[k][n])
}

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

풀이

길이가 (k-1)인 계단 수에 마지막 자리 숫자의 +1, -1한 수를 붙이면 길이가 k인 계단 수를 구할 수 있다.

ex) 12 -> 121, 123

이걸 점화식으로 표현하기 위해 dp[k][i]를 아래와 같이 정의하면,

dp[k][i]: 길이가 k이고, 마지막 자리 숫자가 i인 계단 수의 개수

dp[k][i] = {

               if (i == 0), dp[k-1][i+1]

               if (0 < i < 9), sum(dp[k-1][i+1]) + sum(dp[k-1][i-1])

               if (i == 9), dp[k-1][i-1]

             }

ex) 길이가 4이고 3으로 끝나는 계단 수의 개수는, 길이가 3이고 2로 끝나는 계단 수의 개수와 4로 끝나는 계단 수의 개수를 합한 값

위와 같이 계단 수의 길이를 기준으로 이전 항의 값으로 다음 항의 값을 표현할 수 있고, 키 포인트는 이전 길이의 계단 수들이 어떤 숫자로 끝났는지 기록하는 것이다. 그리고 0과 9로 끝나는 수들은 다른 숫자들과는 다르게 1과 8에서만 파생된다.

이 문제는 다이나믹 프로그래밍 유형으로, 문제 상황을 이전 값으로 다음 값을 표현할 수 있으면 해결이 가능하다. 그걸 어떻게 생각해내느냐는 어릴 때 수학을 열심히 했거나, 머리가 좋거나, 둘 다 아니라면 문제를 많이 풀어보는 수밖에 없는듯 하다.

코드

fun main(){
    val n = readLine()!!.toInt()
    var table = Array(100){IntArray(10)}

    // 한 자리 계단 수는 1~9 한 개씩
    for (i in 1..9){
        table[0][i] = 1
    }
    
    // 길이 2~n까지 n-1번 반복
    repeat(n-1){ k ->
        table[k+1][0] = table[k][1]
        table[k+1][9] = table[k][8]

        for (i in 1..8){
            table[k+1][i] = (table[k][i-1] + table[k][i+1]) % 1_000_000_000
        }
    }

    // 길이 n의 모든 계단 수의 개수를 합한다
    println(table[n-1].toList().reduce{acc, num -> (acc + num) % 1_000_000_000})
}

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

문제유형: DP

접근 방법

DP 문제라는 걸 알고 접근했는데 처음에 해결법이 떠오르지 않았다. 여러 블로그를 참고해서 이해했는데, 그것을 토대로 생각해낸 접근법은 다음과 같다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다. 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

위의 문제 지문에서 힌트를 얻을 수 있는데, 특정 날짜에 상담을 하느냐 안하느냐에 따라 결과가 달라진다.

a[i]의 의미를 i일부터 n일까지 얻을 수 있는 이익이라고 정의한다면, 경우의 수를 2가지로 나눌 수 있다.

1. i일에 일을 안하는 경우
2. i일에 반드시 일을 반드시 하는 경우.

점화식 :  price[i] = max( price[i+1], price[i] + price[ i + time[i] ] )

• if ( n+1 < i + time[i] ) -> price[i] = price[i+1]: 해당 날짜에 상담했을 때 제때 퇴사할 수 없다면, 그 날짜엔 일을 하지 않는다.  

n = 7이고 T[7] = 1일 때 (i + time[i]) = 8 > 7이지만, 7일에도 상담이 가능하다.

따라서, 배열 크기를 n+2, 초기값 price[n+1] = 0으로 초기화 해주면 i = n부터 반복문을 시작할 수 있다.

코드

fun main(){
    val n = readLine()!!.toInt()
    val time = IntArray(n+2)
    val price = IntArray(n+2)

    for (i in 1..n){
        val numbers = readLine()!!.split(" ").map{ it.toInt() }
        time[i] = numbers[0]
        price[i] = numbers[1]
    }
    price[n+1] = 0	// 초기값

    for (i in n downTo 1){
        if ( n+1 < i + time[i] ){	// 예외처리
            price[i] = price[i+1]
            continue
        }

        price[i] = max(price[i+1], price[i] + price[ i + time[i] ])	// 점화식
    }

    println(price[1])
}

리뷰

• dp 기분 문제였지만 해결법을 떠올리고, 풀이를 이해하는 게 쉽지 않았다.
• 바텀업 방식을 하향식으로 생각해볼 수도 있구나.
• 꾸준히 풀어서 익숙해져야지.

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

풀이)

사용할 수 있는 타일은 (1, 00) 2가지이다.

아마 모든 경우의 수를 생각해서 조건문으로 문제를 풀려고 하면 머리가 터질 것이다.

다이나믹 프로그래밍)

사실 이 문제는 다이나믹 프로그래밍으로 유명한 기본 문제인데, 나 역시 DP를 공부하려고 푼 문제다!ㅎㅎ

DP의 핵심 개념은 크게 2가지이다. 

1. 재귀적으로 생각한다. 즉, 작은 문제의 정답은 이미 구해졌다고 믿는다.

2. 불필요한 계산을 줄인다.

(서울대생 분께서 아주 친절하게 설명해주십니다: https://www.youtube.com/watch?v=2RwlzBDhGh4)

1번의 재귀적으로 생각한다는 것은 점화식을 구하는 것과 같다.

타일의 개수는 1)마지막에 반드시 1을 사용하는 경우와 2)반드시 00을 사용하는 경우 2가지로 나눌 수 있는데, 이게 모든 경우의 수를 커버한다.

이것을 점화식으로 표현하면, a(n) = a(n-1) + a(n-2), 초기값은 a(1) = 1, a(2) = 2이 되는데,

a(n)은 타일의 개수가 n일 때, 만들 수 있는 모든 2진수의 가짓수를 의미한다.

피보나치랑 같은 식이 나와서 뭐지? 싶었는데 어이없게도 이게 맞다.

2번의 불필요한 계산을 줄이는 건, 탑다운 방식으로 풀 때는 메모이제이션 방식을, 바텀업 방식에서는 배열에 값을 저장해서 같은 문제의 답을 다시 구하지 않도록 해주면 된다.

이제 이것을 코드로 작성하면 놀랍도록 짧은 코드가 나오게 된다.

코드)

fun main(){
    val n = readLine()!!.toInt()
    val dp = IntArray(1_000_001)	// 크기 n+1로 설정하면, n=1일 때 인덱스 에러 생겨요ㅠㅠ
    dp[1] = 1; dp[2] = 2

    for (i in 3..n){
        dp[i] = (dp[i-2] + dp[i-1]) % 15746 // 점화식
    }
    
    println(dp[n])
}

리뷰)

• 처음에 배열 크기를 n+1로 하면, n=1일 때 인덱스 에러로 틀릴 수 있다.
• 맞아요 그게 저에요.