백준 1937 - 욕심쟁이 판다 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/1937

풀이전략

1. 판다가 더 많은 양의 대나무로 향하는 경로를 찾아야한다.
2. 더 많은 양의 대나무로 향하는 경로의 최대값은 메모이제이션으로 할 수 있기때문에 DP를 이용하지 않으면 시간제한에 걸린다. 따라서 메모이제이션을 해주어야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int a[502][502];
// 메모이제이션을 위한 배열
int dp[502][502];
// 이동을 위한 배열
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int DFS(int r, int c){
    int& ret = dp[r][c];
    if(ret != -1) return ret;
    ret = 1;
    // int ret = sum;

    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        if(a[rr][cc] > a[r][c]){
            ret = max(ret, DFS(rr,cc)+1);
        }
    }

    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    memset(dp, -1, sizeof(dp));
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> a[i][j];
        }
    }

    int res = 0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            res = max(res, DFS(i,j));
        }
    }
    cout << res << endl;
    return 0;
}

소감

아직 시간복잡도를 계산하는 것이 미숙하다. 문제를 보고 DP로 최적화를 할 수 있음은 알았지만, 굳이 해야할 필요를 못느꼈었다. 문제마다 시간복잡도를 더 잘 계산할 수 있도록 공부해야겠다.