욕심쟁이 판다 (feat. 백준, 1937번)

욕심쟁이 판다
https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int N, dx[4], dy[4], arr[500][500], dp[500][500];
int dfs(register int x, register int y, register int pv){
    if(dp[x][y] == 0){
        dp[x][y] = 1;
        for(register int d = 0, nx, ny; d < 4; ++d){    
            nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N || arr[nx][ny] <= pv)
                continue;
            register int tmp = dfs(nx, ny, arr[nx][ny]);
            if(tmp >= dp[x][y])
                dp[x][y] = tmp + 1;
        }
    }
    return dp[x][y];
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    register int ans = 0;
    cin >> N;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            cin >> arr[i][j], dp[i][j] = 0;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            ans = max(ans, dfs(i, j, arr[i][j]));
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

 

1. 하나의 (x,y)을기준으로 생각해볼때 움직일 수 있다면 1, 없다면 0 이 됩니다.
2. 1번의 (x,y)로 이동하기 이전의 위치 ((x-1, y) 또는 (x+1, y) 또는 (x, y - 1) 또는 (x, y + 1)) 는 1번에 의해 (x,y)의 이동값을 알고 있습니다. 따라서 (x,y)로 이동하지 않고 1번에 의해 구해진 값을 그대로 사용합니다. (dp입니다.)
3. 위 과정만 생각해본다면 쉽게 해결됩니다. 어디론가 이동할때 그 지점이 이미 이동했었는지, 했다면 총 이동량은 얼마였는지를 기록하고 읽으면 됩니다.
4. dfs 유형만으로도 풀 수 있으나 시간초과 판정을 받게 됩니다. 따라서 dp 가 필요한 문제입니다.