[Kotlin, S2] 백준 14430번 자원 캐기

출처: unsplash.com

 

자원 캐기(14430번)

Silver 2

#다이나믹 프로그래밍

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

 

문제 내용

 

 

문제 접근

wook이 0, 0에서 n, m까지 이동할 때, 오른쪽, 아래쪽으로만 이동하면서 자원을 캘 수 있을 때, n, m까지 도달했을 때, 얻을 수 있는 자원의 최대 개수를 구해야 한다.

 

얻을 수 있는 최대 자원 개수를 구하는 방법은 입력 예제 1을 예로 설명해 주겠다.

5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0

// init dp array
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

 

처음의 0, 0 부분은 입력값을 그대로 사용한다.

그러면 2차원 array를 모두 0으로 초기화했을 때 0, 0에는 0 또는 1이 오게 될 것이다.

그다음 array에 값을 넣을 때는 넣을 위치의 왼쪽 값과 위쪽 값 중 더 큰 값을 넣어주면 된다. 이동을 오른쪽, 아래쪽으로밖에 이동을 할 수 없기 때문이다.

 

그래서 array의 첫 번째 줄을 구할 때는 위쪽의 값을 확인할 수 없기 때문에 왼쪽 값을 사용해 주면 된다.

그렇게 되면 첫 줄의 입력은 0 1 0 0 이기 때문에 array의 첫 줄의 구성은 아래와 같아진다.

// array의 첫 줄
0 1 1 1

입력의 2번째에 1이 있어서 그 이후의 값도 모두 1이 된다.

이전의 값(왼쪽 값)을 사용하기 때문이다.

 

2번째 줄부터는 위의 값과 왼쪽의 값을 모두 확인해서 더 큰 값을 사용해 주면 된다.

그렇게 끝까지 진행하면 아래와 같은 dp array가 구성된다.

// 최종 array
0 1 1 1
0 1 2 2
1 2 2 2
2 2 3 3
3 4 4 4

 

 

문제 해결 코드

import java.io.InputStreamReader
import java.io.BufferedReader
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (h, w) = readLine().split(" ").map { it.toInt() }
    val dp = Array(h) { Array(w) { 0 } }

    for (i in 0 until h) {
        val mine = readLine().split(" ").map { it.toInt() }

        if (i == 0) dp[i][0] = mine[0]
        else {
            if (mine[0] == 1) dp[i][0] = dp[i-1][0] + 1
            else dp[i][0] = dp[i-1][0]
        }

        for (j in 1 until mine.size) {
            if (i == 0) {
                if (mine[j] == 1) dp[i][j] = dp[i][j-1] + 1
                else dp[i][j] = dp[i][j-1]
            } else {
                if (mine[j] == 1) dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    println(dp.last().last())
}

 

문제 풀이

첫 줄을 입력받을 때는 왼쪽 값만 사용해 준다.

그리고 각 줄의 첫 번째 데이터를 담을 때 위의 값만 사용해 주고 그 이외의 경우는 위와 왼쪽 값을 다시 사용해 준다.

그러면 위에서 언급했다시피 dp array가 구성되게 되고 그 값의 마지막 줄의 마지막 값을 출력한다.

 

 

문제 해결 과정

dp 문제 치고는 생각하는 게 그리 어렵지는 않았다.

2차원 dp 문제의 순한 맛 버전인 듯하다.