[C++] BOJ(백준) 14699 관악산 등산

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

14699번: 관악산 등산

 

n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 구하는 문제다.

쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다.

 

<입력>

쉼터의 개수, 쉼터를 연결하는 길의 개수

쉼터의 높이

쉼터를 연결하는 길의 양 끝 쉼터

 

<출력>

n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수

 

DP를 이용하여 접근했다.처음에는 아래서부터 올라가려 했는데 해당 방법은 시간도 오래 걸리고 DP를 사용하기도 힘들 것 같았다.높은 쉼터부터 접근을 해 아래로 내려오는 방식을 선택했다.

 

1. 쉼터의 높이 순으로 정렬2. 해당 쉼터와 연결된 다른 쉼터의 res값들 중 최댓값을 구함3. 최댓값에 + 1을 현재 쉼터 res에 저장

 

해당 쉼터 보다 낮은 쉼터는 접근한 적이 없기 때문에 res 값이 0

 

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

int n, m;
int res[5001];
pair<int, int> arr[5001];
vector<int> v[5001];

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		arr[i] = { a, i };
	}

	for (int i = 0; i < m; i++) {
		int a, b;	cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	sort(arr + 1, arr + n + 1);

	for (int i = n; i > 0; i--) {
		int ma = 0;
		int index = arr[i].second;
		for (int j = 0; j < v[index].size(); j++)
			ma = max(ma, res[v[index][j]]);
		res[index] = ma + 1;
	}

	for (int i = 1; i <= n; i++) cout << res[i] << "\n";
}

(～￣▽￣)～