[BAEKJOON] 1937 욕심쟁이 판다 (C++)

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

1937번: 욕심쟁이 판다

문제

얼필 보면 dfs 같지만 역시 시간초과가 발생한다.

n*n = 25000, 특정 점을 시작점으로 해서 dfs를 진행하면 25000 * 4 = 100000번의 연산이 필요하고, 모든 점을 시작점으로 dfs를 진행해보려면 25000 * 100000 번의 연산이 필요하므로 시간초과가 날 수 밖에 없다.

따라서 다이나믹 프로그래밍 알고리즘을 이용한다.

풀이

문제를 통해 대나무 양이 적은 곳에서 많은 곳으로만 이동한다는 점을 알 수 있다.

DP[a][b]를 (a,b)지점에 도착할 때까지 거쳐온 지점의 최대개수라고 가정한다.

DP[a][b]의 값은 (a,b)기준 상하좌우 칸의 값 중 최대값 +1 이 된다.

여기서 대나무 양이 가장 적은 칸부터 확인하면서 값을 업데이트 해둔다면, (a,b)주변 값 중 (a,b)로 이동할 수 있는 칸(대나무 양이 더 적은 칸)의 DP값은 이미 최대값으로 업데이트 되어있음을 보장할 수 있다.

따라서 우선순위 큐를 이용해서 대나무 양이 가장 적은 칸부터 좌표값을 추출하여 주변값을 확인하고 DP배열을 업데이트 한다.

업데이트 과정에서 ans값을 최대값으로 갱신한다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"

using namespace std;

int N;
int MAP[505][505];
int DP[505][505];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
priority_queue < pair<int, pair<int, int>>> pq;
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> MAP[i][j]; DP[i][j] = 1;
			pq.push({ -MAP[i][j],{i,j} });
		}
	}
}

void Solve() {
	
	int x, y, xx, yy, val, ans = 0;
	while (!pq.empty()) {
		auto a = pq.top(); x = a.second.second; y = a.second.first; val = -a.first;
		pq.pop();
		ans = max(ans, DP[y][x]);
		for (int i = 0; i < 4; i++) {
			xx = x + dx[i]; yy = y + dy[i];
			if (MAP[yy][xx] > MAP[y][x]) {
				DP[yy][xx] = max(DP[yy][xx], DP[y][x] + 1);
			}
		}
	}

	cout << ans;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();
	return 0;
}

 

푸바오