반응형

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

 

14942번: 개미

자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열을 이용하여 n번 이동했을 때의 노드와 거리를 저장

 

2. n번 이동했을 때 거리가 현재 가지고 있는 에너지보다 작다면 이동

 

3. 에너지가 다 닳을 때까지 이동했을 때 도착한 노드를 출력

 

[ 소스 코드 ]

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n;
int energy[100001];
vector<node> list[100001];
int visited[100001];
int arr[100001][17];
int dist[100001][17];
int H;
 
void dfs(int cur)    //그래프 그리기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next.to] == 1) continue;
        arr[next.to][0] = cur;
        dist[next.to][0] = next.dist;
        dfs(next.to);
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i < H; i++) {        //순서 중요!!!
        for (int j = 2; j <= n; j++) {
            int next = arr[j][i - 1];
            if (arr[next][i - 1] == 0) continue;
            arr[j][i] = arr[next][i - 1];
            dist[j][i] = dist[next][i - 1] + dist[j][i-1];
        }
    }
}
 
int getRomm(int cur)    //최종 도달 방 찾기
{
    int ret = cur;
    int E = energy[cur];
    for (int i = H - 1; i >= 0; i--) {
        if (arr[ret][i] != 0 && dist[ret][i] <= E) {
            E -= dist[ret][i];        //순서 중요!!!
            ret = arr[ret][i];
        }
        if (ret == 1 || E == 0) break;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    H = ceil(log2(n));
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &energy[i]);
    }
 
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    dfs(1);
 
    makeTree();
 
    for (int i = 1; i <= n; i++) {
        printf("%d\n", getRomm(i));
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06

+ Recent posts

티스토리툴바