백준 14699번 관악산 등산(C++)

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

14699번: 관악산 등산

 DP 문제 분류를 못봤으면 풀지 못했을 것 같다.ㅠ

겉보기엔 그래프 탐색 문제로 보인다. 그러나 쉼터의 높이가 백만까지 가능하고 쉼터 수도 무려 5000개나 되기 때문에 이 문제를 일반 그래프 탐색으로 풀면 시간초과가 난다. 일반적인 그래프 탐색도 할 줄 알아야한다.

문제를 잘 파악하는 것이 중요하다. 먼저 중요 키 포인트는 더 높은 곳으로만 올라가야하는 것이다.

즉 가장 높이 있는 쉼터에서는 이동할수 없다. 예를들어 7 5 3 2 순으로 높이가 정해졌다고하면 7에서는 반드시 1이고, 5에서는 7과 닿아있으면 2 아니면 1이다. 

 

이렇게 Top-down 방식으로 가장 높은 쉼터부터 내려가며 DP를 갱신해주면 된다. 두갈래 길이라면 더 높은 DP값을 가져올 것이다.

 

역시 PS를 풀 때는 손으로 80퍼센트는 풀고 들어가는게 맞는 것 같다. 무턱대고 코딩으로 들어가는건 좋지않음을 다시 느꼈다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector<int> shelter[5001];
map<int, int> cost;
int DP[5001] = { 0, };
int N, M;

bool comp(pair<int,int>& a, pair<int,int>& b) {
	return a.second > b.second;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	vector<int> temp;
	for (int i = 1; i <= N; i++) {
		int c;
		cin >> c;
		temp.push_back(c);
		cost.insert(make_pair(i, c)); // 정점, cost
	}

	vector<pair<int, int>> values(cost.begin(), cost.end());
	sort(values.begin(), values.end(), comp);

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		shelter[a].push_back(b);
		shelter[b].push_back(a);
	}

	DP[values[0].first] = 1;

	for (auto iter : values) {// 비용이 비싼 정점부터 탐색
		for (int i = 0; i < shelter[iter.first].size(); i++) {
			if (iter.second < cost[shelter[iter.first][i]])  // 지금 비용보다 비싸면
				DP[iter.first] = max(DP[iter.first], DP[shelter[iter.first][i]] + 1);
		}
		if (DP[iter.first] == 0)
			DP[iter.first] = 1;
	}
	for (int i = 1; i <= N; i++)
		cout << DP[i] << '\n';
}