Difference between r1.1 and the current
@@ -62,6 +62,51 @@
}}}
== 박인서 ==
{{{
#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;
}
}}}
== 곽정흠 ==
@@ -69,6 +114,11 @@
== 15이원준 ==
* 걍 dfs했습니다.
* 약간의 dp를 첨가했습니다.
== 박인서 ==
== 곽정흠 ==
* 걍 dfs했습니다.
* 약간의 dp를 첨가했습니다.
* 1st 아이디어 - 기존의 LIS처럼 일렬로 나열 한 뒤 좌표를 체크하자.(시간복잡도 : O(N^4))
* 2nd 아이디어 - Priority Queue 이용(시간복잡도 상으론 통과지만, 우선순위 큐를 따지기 힘듬)
* 3rd 아이디어 - 자리는 그대로 두고 작은 것부터 순서대로 LIS 사용 (시간복잡도 : O(N^2))
* 3rd 아이디어로 풀었습니다.(원준이와 달리 DFS로 안하고 대나무 수가 작은 곳부터 정렬하여 탐색)
== 곽정흠 ==
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;
}
