백준 14585번 사수빈탕 [DP] :: 마이구미

이번 글은 백준 알고리즘 문제 14585번 "사수빈탕" 을 다뤄본다.

문제는 2017 고려대학교 프로그래밍 대회에서 출제된 문제이다.

문제 풀이는 동적계획법으로 접근할 수 있다.

수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.

오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는 위쪽 (y-좌표가 늘어나는 방향) 또는 오른쪽 (x-좌표가 늘어나는 방향)으로만 움직일 수 있다.

수빈이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

처음에는 하나의 좌표를 기준으로 먼저 먹으면 되겠구나 생각하여 그리디 + 인접행렬 느낌으로 가려고 했다.

하지만 경우의 수가 많이 존재했다.

그래서 결국 동적계획법으로 접근하게 되었다.

하나의 좌표를 기준으로 먹기 위해 가장 빨리 갈 수 있는 경우는 2가지가 된다.

예를 들어 (1, 1) 일 경우를 보자.

이동하기 위해서는 (0, 1), (1, 0) 에서 이동할 수 있다. (즉, x방향, y 방향 이동)

이것을 통해 점화식을 간단히 만들어 낼 수 있다.

dp[x][y] = 좌표 x, y 까지 이동할 때까지 먹은 최대 사탕 개수
dp[x][y] = m(남은 사탕 갯수) + Max(dp[x - 1][y], dp[x][y - 1])

위와 같은 점화식은 이동 좌표에 바구니가 있다면, 현재 남은 사탕과 이전의 최대 사탕 개수를 더해주게 된다.

남은 사탕 개수는 처음 사탕 개수에서 이동 횟수를 빼면 된다. (m - x - y) 

주의할 점은 x 또는 y가 0일 경우 인덱스 에러가 뜨기 때문에 각 경우에 대한 조건 처리가 들어가야한다.

코드를 보면 쉽게 이해할 수 있을 것이라 생각한다.

if (i == 0) {
    if (array[i][j]) {
        dp[i][j] = (m - i - j) + dp[i][j - 1];
    } else {
        dp[i][j] = dp[i][j - 1];
    }
} else if (j == 0) {
    if (array[i][j]) {
        dp[i][j] = (m - i - j) + dp[i - 1][j];
    } else {
        dp[i][j] = dp[i - 1][j];
    }
} else {
    if (array[i][j]) { 
        dp[i][j] = (m - i - j) + Math.max(dp[i - 1][j], dp[i][j - 1]);	
    } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
}

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 14585번 "사수빈탕" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/14585.java