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;
}

박인서

#include <iostream>
#include <vector>
#include <algorithm>
typedef struct abc { int x, y, bam; }point;
std::vector<point> m;
std::vector<int> map[502];
int dp[502][502];

int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i <= n + 1; i++)
		map[0].push_back(0);
	for (int i = 1; i <= n; i++) {
		map[i].push_back(0);
		for (int j = 1; j <= n; j++) {
			point t = { i,j,0 };
			std::cin >> t.bam;
			m.push_back(t);
			map[i].push_back(t.bam);
		}
		map[i].push_back(0);
	}
	for (int i = 0; i <= n + 1; i++)
		map[n + 1].push_back(0);
	std::sort(m.begin(), m.end(), [](point t1, point t2) {return (t1.bam < t2.bam); });

	int res = 0;
	dp[m[0].x][m[0].y] = 1;
	for (int i = 1; i < m.size(); i++) {
		int x = m[i].x, y = m[i].y;
		int max = 1;
		if (max <= dp[x + 1][y] && map[x][y] > map[x + 1][y]) max = dp[x + 1][y] + 1;
		if (max <= dp[x - 1][y] && map[x][y] > map[x - 1][y]) max = dp[x - 1][y] + 1;
		if (max <= dp[x][y + 1] && map[x][y] > map[x][y + 1]) max = dp[x][y + 1] + 1;
		if (max <= dp[x][y - 1] && map[x][y] > map[x][y - 1]) max = dp[x][y - 1] + 1;
		dp[x][y] = max;
		if (res < max) res = max;
	}

	std::cout << res;
	return 0;
}

아이디어

15이원준

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

박인서

• 1st 아이디어 - 기존의 LIS처럼 일렬로 나열 한 뒤 좌표를 체크하자.(시간복잡도 : O(N^4))
• 2nd 아이디어 - Priority Queue 이용(시간복잡도 상으론 통과지만, 우선순위 큐를 따지기 힘듬)
• 3rd 아이디어 - 자리는 그대로 두고 작은 것부터 순서대로 LIS 사용 (시간복잡도 : O(N^2))
• 3rd 아이디어로 풀었습니다.(원준이와 달리 DFS로 안하고 대나무 수가 작은 곳부터 정렬하여 탐색)