[BOJ] 1937번 욕심쟁이 판다

복기

-

코드

• C++ 17

#include <stdio.h>   #define Max(lhs, rhs) ((lhs) > (rhs) ? (lhs) : (rhs))   int N; int Map[502][502]; int Memo[502][502]; // 각 좌표마다 며칠동안 생존 가능한지 메모이제이션한다.   int Search(int r, int c) {     if (Memo[r][c])         return Memo[r][c];       // 상     if (Map[r - 1][c] > Map[r][c])         Memo[r][c] = Max(Memo[r][c], Search(r - 1, c) + 1);     // 하     if (Map[r + 1][c] > Map[r][c])         Memo[r][c] = Max(Memo[r][c], Search(r + 1, c) + 1);     // 좌     if (Map[r][c - 1] > Map[r][c])         Memo[r][c] = Max(Memo[r][c], Search(r, c - 1) + 1);     // 우     if (Map[r][c + 1] > Map[r][c])         Memo[r][c] = Max(Memo[r][c], Search(r, c + 1) + 1);          return Memo[r][c]; }   int main() {     scanf("%d", &N);     for (size_t r = 1; r <= N; r++) for (size_t c = 1; c <= N; c++)         scanf("%d", &Map[r][c]);       int ans = 0;     for (size_t r = 1; r <= N; r++) for (size_t c = 1; c <= N; c++)         ans = Max(ans, Search(r, c) + 1);          printf("%d", ans); }

• C# 6.0

using System;   namespace Csharp {     class Program     {         static int N = 0;         static int[,] Bamboo = new int[502, 502];         static int[,] Memo = new int[502, 502];           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             for (int r = 1; r <= N; r++)             {                 var inputs = Console.ReadLine().Split();                 for (int c = 0; c < N; c++)                     Bamboo[r, c + 1] = Convert.ToInt32(inputs[c]);             }               int ans = 0;             for (int r = 1; r <= N; r++)             {                 for (int c = 1; c <= N; c++)                     ans = Math.Max(ans, Search(r, c) + 1);             }               Console.Write(ans);         }           static int Search(int r, int c)         {             if (0 != Memo[r, c])                 return Memo[r, c];               if (Bamboo[r, c] < Bamboo[r - 1, c])                 Memo[r, c] = Math.Max(Memo[r, c], Search(r - 1, c) + 1);             if (Bamboo[r, c] < Bamboo[r + 1, c])                 Memo[r, c] = Math.Max(Memo[r, c], Search(r + 1, c) + 1);             if (Bamboo[r, c] < Bamboo[r, c - 1])                 Memo[r, c] = Math.Max(Memo[r, c], Search(r, c - 1) + 1);             if (Bamboo[r, c] < Bamboo[r, c + 1])                 Memo[r, c] = Math.Max(Memo[r, c], Search(r, c + 1) + 1);               return Memo[r, c];         }     } }

• Python 3

from sys import stdin, setrecursionlimit setrecursionlimit(1000000) input = stdin.readline   N = int(input()) Map = [ list(map(int, input().split())) for i in range(N) ] Memo = [ [0] * N for i in range(N) ]   def Max(lhs, rhs):     return lhs if lhs > rhs else rhs   def Search(r, c):     global N, Map, Memo       if Memo[r][c]:         return Memo[r][c]       if r > 0 and Map[r - 1][c] > Map[r][c]:         Memo[r][c] = Max(Memo[r][c], Search(r - 1, c) + 1)      if r < N - 1 and Map[r + 1][c] > Map[r][c]:         Memo[r][c] = Max(Memo[r][c], Search(r + 1, c) + 1)     if c > 0 and Map[r][c - 1] > Map[r][c]:         Memo[r][c] = Max(Memo[r][c], Search(r, c - 1) + 1)     if c < N - 1 and Map[r][c + 1] > Map[r][c]:         Memo[r][c] = Max(Memo[r][c], Search(r, c + 1) + 1)       return Memo[r][c]   ans = 0 for r in range(N):     for c in range(N):         ans = Max(ans, Search(r, c) + 1)   print(ans)