[Day 1] 백준 1937 : 욕심쟁이 판다

해법 : 이것도 greedy

음 사실 이것도 처음에 dfs로 뻘 코딩을 했다가 다시 생각해보았다.

사실 제목부터가... 물론 다른 의미지만

왜 greedy같은 형식으로 문제 푸는 것이 가능할까? 판다가 선택하는 기준에 방향성이 있기 때문인 것 같다.

시간복잡도와 내용을 고려해서 한 번 더 고민하는 것이 필요할듯..

 

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
int n;
int A[505][505];
struct tuple2 {
    int x,y,val;
};
tuple2 s[250005];
int _x[4]={1,-1,0,0};
int _y[4]={0,0,1,-1};
int m[505][505];
int _max;
bool sf(tuple2 a,tuple2 b) {
    return a.val>b.val;
}
int main()
{
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    int i,j;
    int cnt=0;
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            scanf("%d",&A[i][j]);
            s[cnt].x=i;
            s[cnt].y=j;
            s[cnt++].val=A[i][j];
        }
    }
    sort(s,s+cnt,sf);
    int imax;
    for(i=0;i<cnt;i++) {

        imax=0;
        for(j=0;j<4;j++) {
            int X=s[i].x+_x[j];
            int Y=s[i].y+_y[j];
            if(X<=0 || X>n || Y<=0 || Y>n) continue;
            if(A[X][Y]>s[i].val) {

                imax=max(imax,m[X][Y]);
            }
        }
        imax+=1;
        _max=max(_max,imax);
        m[s[i].x][s[i].y]=imax;
    }
    printf("%d\n",_max);
    return 0;
}