백준 1937 욕심쟁이 판다 풀이(C++/CPP)

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

문제 접근

• 각 노드에서 DFS로 모든 경우의 수 사용할 경우
  • 모든 노드 : O(N^2)
  • 각 노드에서 DFS할경우, O(V+E) : O(N^2 + 4 * N^2) : O(5*N^2)
  • O(N^2 * 5N^2) = O(5N^4) = 5*625 * e8 > 시간초과
    • DP를 사용, 각 노드 : 판다가 최대한 살수 있는 일수
  • 각 노드에서 값 구하기 위해 DFS 사용
  • 4방향에서 현재보다 값 작을경우, DP 값있으면 반환하고, 없으면 다시 DFS
  • O(V+E) : O(5*N^2)

시간복잡도 계산

• DP 사용하면, 가장 높은 값을 갖는곳으로부터 DFS 한것과 같은 효과
  • O(V+E) = O(N^2 + 4N^2) = O(5*N^2)

인트 계산

• 대나무 양 : 1e6보다 작음 > INT 가능
• DP 값 : 25e4보다 작음 > DP 가능

코드

#include <iostream>
 
using namespace std;
 
int map[510][510];
int dp[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int get_dp(int y, int x) {
    if(dp[y][x] != 0) return dp[y][x];
    
    int rs=0;
    for(int k=0; k<4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        if(map[y][x] < map[ny][nx]) rs = max(rs, get_dp(ny, nx));
    }
    
    return dp[y][x] = rs+1;
}
int main() {
    int N; cin >> N;
    
    fill(&dp[0][0], &dp[509][510], 0);
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            cin >> map[j][i];
        }
    }
    
    int rs=0;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            rs = max(rs, get_dp(j,i));
        }
    }
    
    cout << rs << '\n';
    return 0;
}
 

문제유형

• DP - DFS
  • DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
  • 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

• https://www.acmicpc.net/problem/1520