1R/2016 09 27

오늘의 문제

• 판다

참가자

• 15이원준

코드

15이원준

#include<iostream>

using namespace std;

int arr[502][502] = { 0, };
int dp[502][502] = { 0, };
int ans = 0;
int N;
int search(int x, int y){
  if(dp[x][y] || x <= 0|| y <= 0 || x > N || y > N){
    return dp[x][y];
  }
  int now = 0;

  if(arr[x][y] < arr[x+1][y]){
    dp[x][y] = max(search(x + 1, y) + 1 ,dp[x][y]);
  }
  if(arr[x][y] < arr[x-1][y]){
    dp[x][y] = max(search(x - 1, y) + 1 ,dp[x][y]);
  }
  if(arr[x][y] < arr[x][y+1]){
    dp[x][y] = max(search(x, y + 1) + 1 ,dp[x][y]);
  }
  if(arr[x][y] < arr[x][y-1]){
    dp[x][y] = max(search(x, y - 1) + 1 ,dp[x][y]);
  }
  if(dp[x][y] > ans){
    ans = dp[x][y];
  }
  return dp[x][y];
}
int main(){
  cin>> N;
  for(int i = 1; i<=N; i++){
    for(int j = 1; j <= N; j++){
      int tmp;
      scanf("%d", &tmp);
      arr[i][j] = tmp;
    }
  }
  for(int i = 1; i<=N; i++){
    for(int j = 1; j <= N; j++){
      if(!dp[i][j]){
        search(i,j);
      }
      //cout<< dp[i][j] << " ";
    }
    //cout<<endl;
  }
  cout<< ans + 1 <<endl;
}

아이디어

15이원준

• 걍 dfs했습니다.
• 약간의 dp를 첨가했습니다.