반응형

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

 

13418번: 학교 탐방하기

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들고, node arr [ 500000 ] 배열을 만들어 각각의 A, B, C를 저장합니다. 이때, 오르막길이 0이므로 0이 입력되면 C = 1, 1이 입력되면 C = 0으로 저장합니다.

 

2. arr를 오름차순으로 정렬하고, vect 배열을 초기화한 후 Union-Find를 이용하여 각 노드들을 이어주고, cost를 max에 더해줍니다.

 

3. arr를 내림차순으로 정렬하고, vect 배열을 초기화한 후 Union-Find를 이용하여 각 노드들을 이어주고, cost를 min에 더해줍니다.

 

4. max * max - min * min을 출력해줍니다.

 

[ 소스코드 ]

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int A;
    int B;
    int cost;
};
 
struct Greater {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
struct Less {
    bool operator()(node right, node left) {
        return left.cost > right.cost;
    }
};
 
int N, M;
int vect[1001];
node arr[500000];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
ll fatigue(ll a)
{
    ll ret = a;
 
    for (int i = 1; i <= M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int cost = arr[i].cost;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ret += cost;
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i <= M; i++) {
        scanf("%d %d", &arr[i].A, &arr[i].B);
        int cost;
        scanf("%d", &cost);
        if (cost == 0) {
            arr[i].cost = 1;
        }
        else {
            arr[i].cost = 0;
        }
    }
 
    ll max, min;
 
    for (int i = 0; i <= N; i++) {
        vect[i] = i;
    }
 
    vect[1] = 0;
 
    sort(arr + 1, arr + M + 1, Greater());
 
    max = fatigue(arr[0].cost);
 
    for (int i = 0; i <= N; i++) {
        vect[i] = i;
    }
 
    vect[1] = 0;
 
    sort(arr + 1, arr + M + 1, Less());
 
    min = fatigue(arr[0].cost);
 
    printf("%lld", max * max - min * min);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
반응형

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

 

9463번: 순열 그래프

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 둘째 줄과 셋째 줄에는 두 순열이 주어진다. 순열은 {1, 2, ..., n}으로 이루어져 있고, 공백으로 구분

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 첫 줄의 num을 입력받고, arr [ num ] = i로 저장합니다.

 

2. 두 번째 줄의 num을 입력받고, arr [ num ]을 idx로 세그먼트 트리를 갱신합니다.

 

3. arr [ num ] + 1부터 n까지 구간 합을 ans에 더해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int T;
ll segTree[263000];
int arr[100001];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n;
        scanf("%d", &n);
        fill_n(segTree, 263000, 0);
        
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            arr[num] = i;
        }
 
        ll ans = 0;
 
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            updateTree(1, 1, n, arr[num]);
            ans += sumTree(1, 1, n, arr[num] + 1, n);
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
반응형

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

 

10090번: Counting Inversions

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 입력받은 수를 인덱스로 segment tree를 업데이트합니다.

 

2. 입력받은 수 + 1부터 N까지 구간 합을 ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll segTree[2100000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    ll ans = 0;
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
 
        updateTree(1, 1, N, n);
        ans += sumTree(1, 1, N, n + 1, N);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
반응형

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

 

1615번: 교차개수세기

첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 입력받은 수를 첫번 째 수를 기준으로 오름차순으로 정렬합니다.

 

2. for문을 통해 반복하면서 두번 째 수를 인덱스로 segment tree를 업데이트 합니다.

 

3. 이후 두번 째 수부터 N까지 구간 합을 ans에 더해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N, M;
pair<int, int> arr[2000000];
ll segTree[5000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node] += 1;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    sort(arr, arr + M);
 
    ll ans = 0;
 
    for (int i = 0; i < M; i++) {
        int cur = arr[i].second;
        
        updateTree(1, 1, N, cur);
        ans += sumTree(1, 1, N, cur + 1, N);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18

+ Recent posts

티스토리툴바