Baekjoon 1937번 욕심쟁이 판다

문제

https://www.acmicpc.net/problem/1937

걸린 시간

00 : 28 : 48

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int forest[500][500];
int cache[500][500];

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int dp(int y, int x){
    // 메모이제이션
    int& ret = cache[y][x];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = 1;
    for(int i = 0; i < 4; i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(0 <= ny && ny < n && 0 <= nx && nx < n)
            if(forest[y][x] < forest[ny][nx])
                ret = max(ret, dp(ny, nx)+1);
    }
    return ret;
}

int solve(){
    int ans = 0;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < n; x++)
            ans = max(ans, dp(y, x));
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> forest[i][j];
    memset(cache, -1, sizeof(cache));
    cout << solve();
    return 0;
}

모든 지점에서 이동할 수 있는 최대 경로를 찾는 완전 탐색의 경우 O(n⁴) 복잡도를 가지며 최대 500⁴ = 62,500,000,000 번으로 시간초과가 난다.

대나무 숲 속 현재 위치에서 움직일 수 있는 최대값을 캐쉬에 저장하는 메모이제이션을 적용할 경우 복잡도는 O(n²) 로 줄어든다.