백준 1937(욕심쟁이 판다)

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

1937번: 욕심쟁이 판다

 

무슨 문젠지 모르겠는 문제 

 

그냥 dp인걸 알아서 풀었다 정도?

 

ㅈ 같은 판다

 

아무튼 생각을 진짜 많이 했다. 집중해서 계속 하다보니깐 떠오른 사실이 있었다. 

 

가장 큰 값 순서대로 처리하면 꼬일 일이 없다.

 

여기서 말하는 꼬일 일이란 내가 만약에 큰 값대로 처리를 하는데 어떤 값 처리 후에 그 값의 dp변화가 생기는 것이다. 

예제에서 가장 큰 값인 16을 먼저 처리해보자. 16 상 하 좌 우 에는 아무리 봐도 16보다 큰 값이 존재하지 않는다. 

그래서 dp값을 1로 유지한다. 

 

그 뒤에 15 14 13 12 이런식으로 처리를 한다.

 

11을 처리하는 경우로 가보자 주변에 15가 있다. 11의 dp값은 15를 이은 값이므로 2가 된다. 

이렇게 반복을 했을때, 꼬이는 경우가 전혀 생각나지 않았다. 그래서 채택하고 코드를 구현했다. 

 

 

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define MAX 501

int n, res = -1;
int leaf[MAX][MAX];
int dp[MAX][MAX];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
priority_queue<pair<int, pair<int, int> > > pq;
pair<int, pair<int, int> > p;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> leaf[i][j];
			dp[i][j] = 1;
			pq.push(make_pair(leaf[i][j], make_pair(i, j)));
		}
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		int num = p.first;
		int x = p.second.first;
		int y = p.second.second;
		for (int i = 0; i < 4; i++) {
			if (x + dx[i] < 0 || y + dy[i] < 0 || x + dx[i] >= n || y + dy[i] >= n) continue;
			if (leaf[x + dx[i]][y + dy[i]] > num) {
				dp[x][y] = max(dp[x][y], dp[x + dx[i]][y + dy[i]] + 1);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			res = max(res, dp[i][j]);
		}
	}
	cout << res << "\n";
}

 

 

dp는 너무 어렵다 .. dp인걸 알아서 이 정도지