• 15이원준

# 3. 코드 ¶

## 3.1. 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;
}

```

## 3.2. 박인서 ¶

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

# 4. 아이디어 ¶

## 4.1. 15이원준 ¶

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

## 4.2. 박인서 ¶

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