[14585번] 사수빈탕

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

이 문제는 DP로 해결이 가능하다.

map이라는 배열에는 사람이 x,y에 도착했을 때 결국 m - y - x개의 사탕을 사탕바구니에서 얻을 수 있게된다.

따라서 그 내용을 모두 map에 저장해두고 dp를 돌려보자.

dp점화식은 다음과 같다.

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + map[i][j];

이 의미는 j,i 번째의 dp값은 위에서 내려온 값 dp[i - 1][j]과 왼쪽에서 온 값 dp[i][j - 1]값 중 최대에 현재 map[i][j]가 가지고 있는 값을 더한 것을 의미한다.

이 문제는 [5419번] 북서풍 : https://www.acmicpc.net/problem/5419 문제와 매우 비슷하나 북서풍 문제는 y범위가 -10억~10억이어서

dp로 해결이 불가능하고, 이 문제는 dp로 해결이 가능하다는 차이가 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int map[302][302]; long long dp[302][302];   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)     {         int x, y;         scanf("%d %d", &x, &y);           map[y+1][x+1] = m - y - x;     }            for (int i = 1; i <= 301; i++)         for (int j = 1; j <= 301; j++)             dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + map[i][j];       cout << dp[301][301];          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus