알고리즘) 백준 Baekjoon 1937번 욕심쟁이 판다(dynamic programming)

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

'욕심쟁이 판다' 문제는 LIS와 유사한 dynamic programming 문제입니다. LIS와 다른점은 방향이 4개가 존재하며, 연속적으로 큰 수를 가져야만 판다가 살수 있는 날이 +1 count 됩니다.

판다가 살수 있는 최대 날짜를 구하기 위해서는 모든 y, x지점에서 시작해야하며 map[y][x]에서 시작했을 때 map[dy][dx]의 숫자가 더 커야만 살 수 있는날을 하루 늘려주게 됩니다.
LIS와 마찬가지로 재귀함수와 메모이제이션를 이용해서 문제를 해결했습니다.

알고리즘 자체는 간단합니다.
1. 시작지점에서 동, 서, 남, 북 4방향을 살펴 봅니다.
2. 4방향 중 숫자가 큰 y, x 를 재귀함수로 call한 후 +1 해줍니다.
3. 더 큰 숫자가 나타나지 않을 때까지 재귀함수를 call한 후 가장 큰 숫자를 저장하여 출력합니다.

단 여기서 반드시 메모이제이션을 해야 시간초과 없이 수행 할 수 있습니다.

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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

int findLivingDay(int y, int x) {     int &ret = cache[y][x];       if (ret != -1) return ret;       ret = 1;       for (int i = 0; i<4; i++)     {         int ry = y + dy[i];         int rx = x + dx[i];           if (map[y][x] < map[ry][rx])         {             ret = max(ret, findLivingDay(ry, rx) + 1);         }     }       return ret; }   int main() {     for (int i = 0; i < 501; i++)     {         for (int j = 0; j < 501; j++)         {             cache[i][j] = -1;         }     }       cin >> n;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             cin >> map[i][j];         }     }       int ret = 0;     for (int y = 0; y < n; y++)     {         for (int x = 0; x < n; x++)         {             ret = max(ret, findLivingDay(y, x));         }     }       cout << ret << endl; } Colored by Color Scripter

cs