Boj 14585 사수빈탕 C++

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

 

 

문제

 

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

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

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

 

 

조건

(0 ≤ N ≤ 300, 1 ≤ M ≤ 1,000,000, 0 ≤ xi, yi ≤ 300)

 

풀이

 

수빈이는 x좌표, y좌표가 늘어나는 방향으로만 움직일 수 있기 때문에 격자 그래프 상에서 이전상태는 2가지 뿐이다.

이전 상태에 의해서 다음 상태가 정해진다는 조건을 만족시키기 때문에 dp 풀이가 가능하다.

이때 dp 배열의 정의는  dp[i][j] = 수빈이가 i, j 번째 칸 까지 이동했을 때 먹을 수 있는 사탕의 최대 개수이다.

이때, (i, j) 칸에 사탕이 있으면 먹는 것이 가장 이득이다.

사탕은 한칸 이동할 때마다 하나씩 녹으므로 max(candy[i][j] - i - j,  0) 이다.

 

고로, 최종적인 점화식은 dp[i][j] = max(candy[i][j] - i - j, 0) + max(dp[i-1][j], dp[i][j-1]) 가 된다.

 

(0, 0) 칸에는 사탕이 없으며, 수빈이는 (0, 0) 부터 시작하므로 0번째 인덱스의 배열을 따로 채워줘야 한다는 것을 잊으면 안된다.

 

 

전체코드

 

 

#include <iostream>
using namespace std;

int dp[301][301], candy[301][301];

int main() {

    int N, M;
    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        candy[x][y] = M;
    }
    for(int i = 1; i <= 300; i++) {
        dp[0][i] = max(candy[0][i] - i, 0) + dp[0][i-1];
        dp[i][0] = max(candy[i][0] - i, 0) + dp[i-1][0];
    }
    for(int i = 1; i <= 300; i++) {
        for(int j = 1; j <= 300; j++) {
            dp[i][j] = max(candy[i][j]-i-j, 0) + max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[300][300];
}