[BaekJoon, C++] 14585번 - 사수빈탕

 

 

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

14585번: 사수빈탕

 

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int n,m;

int Candy[301][301];

int dp[301][301];

int main()
{
  cin>>n>>m;

  for(int i=0; i<n; i++){
    int x,y;
    cin>>x>>y;
    Candy[x][y] = m - (x+y);
    if(Candy[x][y] < 0){
      Candy[x][y] = 0;
    }
    dp[x][y] = Candy[x][y];
  }

  int max_candy = 0;


  for(int i=1; i<300; i++){
    for(int j=1; j<300; j++){
      dp[j][i] = Candy[j][i] + max(dp[j-1][i], dp[j][i-1]);
      max_candy = max(dp[j][i], max_candy);
    }
  }

  cout<<max_candy;

}

 

 

수빈이는 ( 0 , 0 )에서 시작해서 위쪽, 오른쪽 방향으로밖에 움직이지 못한다.

Candy 배열 : ( x , y )에 바로 도달하면 m개 사탕에서 x+y 개의 사탕이 녹는 걸 구현하고 dp에 담아놓는다.

 

위쪽, 오른쪽 방향밖에 못 움직이므로

( j , i ) 위치에서의 사탕 개수 = ( j-1 , i ) 와 ( j , i-1 ) 중에서 큰 것 + ( j , i ) 에서의 Candy 로 구한다.