욕심쟁이 판다 / 다이나믹 프로그래밍, DP, 알고리즘, deque

욕심쟁이 판다

분류  : DP

난이도  : 3 / 5

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

평

처음에는 스택을 이용한 방법으로 접근을 하였다. 모든 좌표에 대해서 스택에 넣고 팝을 하면서 좌우상하 네 방향을 모든 진행하면서 갈 수 있는 최대 depth를 측정하였다.

하지만, 정상적인 기능을 하지만 시간이 오래 걸렸다. 그래서 가지치기를 이미 계산이 된 부분은 하지 않도록 설정하였으나 그래도 시간 제한에 걸려버렸다.

그래서 전면 수정 리컬시브를 통한 DP로 푸는 방향으로 방향을 전환.

#include<iostream> #define max(a,b) a>b ? a : b #pragma warning(Disable:4996) #define MAX 501 using namespace std; int N; int A[MAX][MAX]; int D[MAX][MAX]; int Dy[4] = { 0, 1, 0, -1}; // int Dx[4] = { 1, 0, -1, 0 }; // 우 하 좌 상 int move(int x, int y) { if (D[y][x] == 0) { // D가 0인 경우는 아직 계산이 되지 않았다. D[y][x] = 1; // 계산할때 하루 인정. for (int i = 0; i<4; i++) { // 4방향에 대해서 갈 수 있는지 판단한다. int ny = Dy[i] + y; int nx = Dx[i] + x; if (ny < 1 || nx<1 || ny > N || nx > N) continue; // 범위를 벋어나는 경우 if (A[y][x] <= A[ny][nx]) continue; // 문제 조건에 의해 진행을 못하는 경우 // nx, ny로 움직일 수 있다면, 현재의 D와 다음 이동의 리턴 값 + 1 과 비교 D[y][x] = max(D[y][x], move(nx, ny) + 1); } } // 아무것도 이동할 수 없다면 기존의 값 1을 리턴할 것이고, // 다른 것으로 이동할 수 있다면, 이동으로 계산된 D값을 리턴할 것이다. return D[y][x]; } int main() { cin >> N; // input을 받으면서 D값을 모두 0로 초기화한다. for (int i = 1; i<=N; i++) { // i > y for (int j = 1; j<=N; j++) { // j > x cin >> A[i][j]; D[i][j] = 0; } } // 결과값을 -1로 초기화하고 모든 지점에 대해서 결과를 계산한다. int ans = -1; for (int i = 1; i<=N; i++) { for (int j = 1; j<=N; j++) { ans = max(move(j, i), ans); } } cout << ans << endl; }

길찾기류의 문제를 풀때는 리컬시브를 활용하는 것이 짜세라는 걸 다시 한번 깨닭았다...

또, 문제에 따라 다양하게 변화를 줄 수 있다.

dx, dy의 배열 순서를 조절해서 방향에 대해 우선순위를 세울 수 있다 !