반응형

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

 

14699번: 관악산 등산

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ 5001 ]을 선언하고 -1로 초기화해 줍니다.

 

2. 1번 노드부터 N번 노드까지 dfs를 돌면서 갈 수 있는 쉼터의 최댓값을 다음의 점화식을 이용하여 dp[ i ]에 저장합니다.

dp[ i ] = max( dp[ i ], dfs(next) + 1 )

 

3. 1번 노드부터 N번 노드까지 dfs( i )를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
int H[5001];
int dp[5001];
vector<int> list[5001];
 
int dfs(int cur)
{
    if (dp[cur] != -1) return dp[cur];
    int& ret = dp[cur];
    ret = 1;
 
    for (auto& next : list[cur]) {
        if (H[cur] < H[next]) {
            ret = max(ret, dfs(next) + 1);
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
        dp[i] = -1;
    }
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    for (int i = 1; i <= N; i++) {
        cout << dfs(i) << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14

+ Recent posts

티스토리툴바