백준 14585번: 사수빈탕

문제: https://www.acmicpc.net/problem/14585

문제 풀이

DP

dp[i][j] = 좌표 (i, j)에 도달했을 때 먹을 수 있는 사탕의 최대 개수

answer = 먹을 수 있는 사탕의 최대 개수

1초에 오른쪽 또는 위쪽으로만 이동이 가능함

그러면 좌표에 도달하려면 왼쪽 또는 아래쪽 좌표에서 도달해야 함

따라서 왼쪽, 아래쪽 좌표를 도달했을 때 먹을 수 있는 사탕의 최대 개수를 알면 현재 좌표에 도달했을 때 먹을 수 있는 사탕의 최대 개수를 구할 수 있음

N개의 사탕 바구니에 M개의 사탕이 있는데 1초마다 모든 바구니의 사탕이 1개씩 녹음

시작위치가 (0, 0)이므로 위치 (y, x)에 도달하는데 y + x초가 걸리므로 해당 위치에 사탕 바구니가 있으면 도달하면 사탕이 M - y - x개 남음

y + x가 M보다 작을때만 사탕이 남아있으므로 이때만 dp[y][x]에 M - y - x를 저장함

모든 좌표 (i, j)에 대해 왼쪽, 아래쪽 좌표의 dp 값을 확인해 더 큰 값을 dp[i][j]에 더해 현재 좌표에 도달했을 때 먹을 수 있는 사탕의 최대 개수를 반영함

dp[i][j]를 구할때마다 최댓값을 answer에 저장하면 문제에서 구하는 먹을 수 있는 사탕의 최대 개수가 저장되므로 출력하면 정답

풀이 설명

좌표 평면 상에 N개의 사탕 바구니가 있고 사탕 바구니에는 M개의 사탕이 들어있다. 수빈이는 (0, 0)에 있고 1초에 한번 오른쪽 또는 위쪽으로 이동할 수 있다. 1초마다 모든 사탕 바구니의 사탕이 한 개씩 녹으며 수빈이가 사탕 바구니의 위치로 이동했을 때 남아있는 사탕을 순식간에 모두 먹을 수 있다면 먹을 수 있는 사탕의 최대 개수를 구하는 문제이다.

1초마다 좌표를 오른쪽 또는 위쪽으로만 이동할 수 있으므로 특정 좌표를 도달하려면 해당 좌표의 아래쪽, 왼쪽에서만 도달할 수 있다. 따라서 해당 좌표의 아래쪽, 왼쪽 좌표에 도달했을 때 먹을 수 있는 사탕의 최대 개수를 알고 있다면 해당 좌표에 도달했을 때 먹을 수 있는 사탕의 최대 개수도 구할 수 있으므로 문제를 DP로 풀 수 있다.

이에 따라 (y, x)좌표에 도달했을 때 먹을 수 있는 사탕의 최대 개수를 dp[y][x]에 저장하면 되는데 이때 사탕 바구니가 없는 칸이라면 초기값을 0으로 초기화하면 되고 사탕 바구니가 있다면 사탕이 M개가 있지만 해당 좌표에 y + x초에 도달할 수 있으므로 M개에서 시간만큼 빼주어야 한다.

그러나 y + x가 M보다 크다면 도달할 때 사탕이 모두 없어지므로 M보다 작을때만 M - y - x를 dp[y][x]에 저장한다.

그 이후에 모든 좌표 (i, j)에 대해 왼쪽 칸, 아래쪽 칸을 확인해 dp 배열의 값이 더 큰 값을 dp[i][j]에 더해주면 모든 칸에 대해 해당 좌표에 도달할 때 먹을 수 있는 사탕의 최대 개수를 저장할 수 있다.

그러므로 모든 칸을 계산하면서 해당 좌표의 dp값 중 최댓값을 answer에 저장하면 문제에서 찾는 먹을 수 있는 사탕의 최대 개수이므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val M = nextInt()
    val dp = Array(301){IntArray(301)}
    var answer = 0
    for(i in 0 until N){
        val x = nextInt()
        val y = nextInt()
        if(x + y < M){
            dp[y][x] = M - x - y
        }
    }
    for(i in 0..300){
        for(j in 0..300){
            if(i > 0 && j > 0){
                dp[i][j] += maxOf(dp[i - 1][j], dp[i][j - 1])
            } else if(i > 0){
                dp[i][j] += dp[i - 1][j]
            } else if(j > 0){
                dp[i][j] += dp[i][j - 1]
            }
            answer = maxOf(answer, dp[i][j])
        }
    }
    println(answer)
}