[C++] 백준 1937 욕심쟁이 판다

1937 욕심쟁이 판다

1937번: 욕심쟁이 판다

C++

#include <iostream>
#include <algorithm>

using namespace std;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n;
int DAE[503][503];  // 대나무 숲의 정보
int DP[503][503];   // Dynamic Programming

int DPP(int x, int y) {
    if (DP[x][y]) return DP[x][y];

    DP[x][y] = 1;

    for (int i = 0; i < 4; i++) {
        int X = x + dx[i], Y = y + dy[i]; // 대문자: 이동 후 좌표

        if ((0 <= X && X < n) && (0 <= Y && Y < n))
            if (DAE[x][y] < DAE[X][Y])
                DP[x][y] = max(DP[x][y], DPP(X, Y) + 1);
    }
    return DP[x][y];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = 0;

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> DAE[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = max(ans, DPP(i, j));

    cout << ans << '\n';

    return 0;
}

 

DP[x][y]는 (x, y) 지점에서의 최대 생존 일수를 의미한다. DFS 개념을 이용해서, DP[x][y]가 0이 아니라면 해당 값 반환,

0이라면 1로 설정해준다. 

DP[x][y] = DP[x + dx][y+dy] 중의 최대값 (dx, dy는 상하좌우 x,y좌표 변량)의 방식으로 풀이하였다.

 

최대 일수 결과값을 구할 때 이중 for문을 통해 각 시작점 중 어느 시작점이 최선인지를 확인해야 한다.