14699 관악산 등산

오늘 풀어야 하는 문제는 다 풀어서 오늘 풀건 아니고.. (오늘 저녁에는 벽 부수기로 함)

 

내일을 위해 미리 읽어두자 싶었음

 

으음... 어음.... 완전탐색 밖에 안 떠오른다

 

시작하는 지점을 달리해서 dfs로 확인하기....

 

근데 최악의 경우 n = 5000, m = 100,000이고 그럼 완전탐색하면 O(n + m)이라 105,000

 

이걸 각 노드마다 확인하면 5,000 * 105,000 음 500,000,000 5억번! 터질 것 같은데....

 

 

---

아 문제를 대충 읽어서 모든 노트 안 찾아도 되는 줄 알았는데 모든 노드에서 출발할 경우 다 찾아야 하는구나

 

그리고 이걸 도저히 어떻게 할지 몰라서 걍 문제 분류 봤음ㅋㅋ

 

DP로 풀어야 했다

 

DP..? 메모이제이션이다 

 

누가 DP로 지었냐고 진짜 

 

암튼.. 이걸 계속 계산하면 시간복잡도 터지니깐! 계산한 걸 저장해놓고 그걸 활용하도록 하자

 

 

ㅋㅋㅋ 하지만 도저히 모르겠음

 

저걸 더해가면 되는 거 같은데 어떻게 더해갈지 모르겠다... 그래서 고민하다가 다른사람 코드 참고해서 풀었음

 

아..! 이걸 높은 곳만 올라갈 수 있으니 단방향 그래프로 변환하는구나

 

 

 

신기해 

 

하지만 머리로는 이해 되는데 와닿지는 않음,,

 

이런 유형 문제 더 만나다보면 익숙해지겠지,,, 그래프 + dp는 아직 어색,, 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

vector<int> adj[5005];
int         dp[5005];
int         height[5005];

int dfs(int curr)
{
    if (dp[curr] != 0)
        return dp[curr];

    for (int i = 0; i < adj[curr].size(); i++)
        dp[curr] = max(dp[curr], dfs(adj[curr][i]));
    return (++dp[curr]);
}

int     main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> height[i];

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;

        if (height[x] < height[y])
            adj[x].push_back(y);
        else
            adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        cout << dfs(i) << "\n";
    
    return 0;
}