반응형

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

 

18116번: 로봇 조립

성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 cnt 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. cnt 배열을 모두 1로 초기화하고, vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 cnt 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N;
int vect[1000001];
int cnt[1000001];
 
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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    
    for (int i = 1; i < 1000001; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < N; i++) {
        char cmd;
        cin >> cmd;
 
        if (cmd == 'I') {
            int a, b;
            cin >> a >> b;
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
        }
        else {
            int a;
            cin >> a;
 
            cout << cnt[Find(a)] << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
반응형

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

 

2934번: LRH 식물

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 L + 1 부터 R - 1 까지 1을 더해주고, L노드와 R노드의 값에 이전에 핀 꽃의 개수인 cnt[ L ] + cnt[ R ]의 값을 빼고, 그 값을 출력합니다.

 

2. cnt[ L ]의 값과 cnt[ R ]의 값을 갱신해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int segTree[262222];
int lazy[262222];
int cnt[100001];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node]++;
 
        if (s != e) {
            lazy[node * 2]++;
            lazy[node * 2 + 1]++;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (s > idx || e < idx) return 0;
    if (s == e) return segTree[node];
 
    int m = (s + e) / 2;
    int left = getTree(node * 2, s, m, idx);
    int right = getTree(node * 2 + 1, m + 1, e, idx);
 
    return  left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int L, R;
        scanf("%d %d", &L, &R);
 
        if (L + 1 <= R - 1) {
            updateTree(1, 1, 100000, L + 1, R - 1);
        }
 
        int tempL = getTree(1, 1, 100000, L);
        int tempR = getTree(1, 1, 100000, R);
 
        printf("%d\n", tempL + tempR - cnt[L] - cnt[R]);
 
        cnt[L] = tempL;
        cnt[R] = tempR;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
반응형

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

 

14245번: XOR

첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 초기 배열을 arr 배열에 저장합니다.

 

2. segmentTree의 리프 노드에 arr 배열의 값들을 넣습니다.

 

3. 느리게 갱신되는 세그먼트 트리를 이용하여 lazy 배열의 값들에 XOR한 값을 저장합니다.

 

4. 해당 쿼리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, m;
int segTree[1050000];
int lazy[1050000];
int arr[500000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e)/2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] ^= lazy[node];
 
        if (s != e) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int a)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] ^= a;
        if (s != e) {
            lazy[node * 2] ^= a;
            lazy[node * 2 + 1] ^= a;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, a);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, a);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || e < idx) return;
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 0, n - 1);
 
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
 
            updateTree(1, 0, n - 1, a, b, c);
        }
        else {
            int a;
            scanf("%d", &a);
 
            getTree(1, 0, n - 1, a);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
반응형

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

 

3006번: 터보소트

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. segmentTree의 리프노드를 모두 1로 채우고 나머지 노드들을 구간합으로 채워줍니다.

 

2. 배열을 입력 받고, 각 수의 위치를 arr 배열에 저장합니다.

 

3. 1부터 N까지 번갈아가며 홀수번째 단계에서는 0 ~ arr[ i ] - 1까지의 구간합을 출력하고, 짝수번째 단계에서는 arr[ i ] + 1 ~ 2N - 1까지의 구간합을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100001];
int segTree[200000];
 
void updateTree(int idx, int k)
{
    while (idx != 0) {
        segTree[idx] += k;
        idx >>= 1;
    }
}
 
int getTree(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        updateTree(N + i, 1);
 
        arr[n] = i;
    }
 
    int L = 1;
    int R = N;
    int cnt = 1;
 
    while (L <= R) {
        if (cnt & 1) {
            printf("%d\n", getTree(N, N + arr[L]) - 1);
            updateTree(N + arr[L], -1);
            L++;
        }
        else {
            printf("%d\n", getTree(N + arr[R], 2 * N - 1) - 1);
            updateTree(N + arr[R], -1);
            R--;
        }
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
반응형

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

 

1280번: 나무 심기

첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. segmentTree를 두개 만들어서 하나에는 모든 좌표의 합을 저장하고, 나머지 하나에는 나무의 개수를 저장합니다.

 

2. idx를 입력 받으면 두 segmentTree를 업데이트 해주고, 0 ~ idx - 1과 idx + 1 ~ 200000까지의 좌표의 합과 나무 개수를 이용하여 모든 나무까지의 거리를 구합니다.

 

3. 현재 좌표의 왼쪽 나무들까지의 합을 구할 때는 현재 좌표 * 나무 개수 - 왼쪽 나무의 좌표들의 합으로 구하고, 오른쪽 나무들까지의 합을 구할 때는 오른쪽 나무의 좌표들의 합 - 현재 좌표 * 나무의 개수를 더해 구합니다.

 

4. ans에 3에서 구한 값을 곱해주고 1,000,000,007로 모듈러 연산을 한 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
#define M 1000000007
 
using namespace std;
 
int N;
ll segTree[400002];
ll segTree2[400002];
ll ans = 1;
 
void updateTree(ll idx)
{
    ll temp = idx - 200001;
 
    while (idx != 0) {
        segTree[idx] += temp;
        segTree2[idx]++;
        idx >>= 1;
    }
}
 
pair<ll,ll> getTree(int l, int r)
{
    ll ret = 0;
    ll ret2 = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            ret2 += segTree2[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            ret2 += segTree2[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return { ret, ret2 };
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        ll idx;
        scanf("%lld", &idx);
        pair<ll, ll> temp;
        pair<ll, ll> temp2;
 
        updateTree(idx + 200001);
 
        if (i != 0) {
            if (idx == 0) {
                temp = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp.first - idx * temp.second) % M)) % M;
            }
            else if (idx == 200000) {
                temp = getTree(200001, 200001 + idx - 1);
                ans = ((ans % M) * ((idx * temp.second - temp.first) % M)) % M;
            }
            else {
                temp = getTree(200001, 200001 + idx - 1);
                temp2 = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp2.first - idx * temp2.second + idx * temp.second - temp.first) % M)) % M;
            }
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
반응형

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

 

2517번: 달리기

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr 배열에 실력을 저장하고, vector<int> list에 실력을 저장하고, 오른차순으로 정렬합니다.

 

2. for문으로 arr배열을 돌면서 lower_bound를 활용하여 해당 실력이 몇번 째 순서인지 확인하고, segmentTree를 업데이트 해줍니다.

 

3. query를 이용하여 해당 실력부터 가장 실력이 높은 값까지 합을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
vector<int> list;
int arr[500001];
int segTree[1000000];
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx] += 1;
        idx >>= 1;
    }
}
 
int query(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
 
        list.push_back(a);
        arr[i] = a;
    }
 
    sort(list.begin(), list.end());
 
    for (int i = 0; i < N; i++) {
        int cur = lower_bound(list.begin(), list.end(), arr[i]) - list.begin();
 
        updateTree(cur + N);
 
        printf("%d\n", query(N + cur, 2 * N - 1));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
반응형

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

 

17612번: 쇼핑몰

입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 이용하여 계산대로 들어가는 순서를 정합니다.

 

2. priority_queue에서 하나씩 빼고 넣으면서 뺀 값을 vector<node> 에 넣습니다.

 

3. 계산대에서 나오는 순서대로 vector<node>를 정렬합니다.

 

4. vector<node>를 for문을 통해 돌면서 주어진 대로 계산해 ans에 저장합니다.

 

5. 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
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int K;
    ll num;
    int w;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (left.w == right.w) return left.K < right.K;
        return left.w < right.w;
    }
};
 
int N, k;
vector<node> seq;
 
bool cmp2(node left, node right)
{
    if (left.w == right.w) return left.K > right.K;
    return left.w < right.w;
}
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    queue<pair<ll,int>> q;
    scanf("%d %d", &N, &k);
 
    for (int i = 0; i < N; i++) {
        int b;
        ll a;
        scanf("%lld %d", &a, &b);
        q.push({a,b});
    }
 
    for (int i = 1; i <= k; i++) {
        pq.push({ i,q.front().first,q.front().second });
        q.pop();
 
        if (q.empty()) break;
    }
 
    ll ans = 0;
 
    while (!pq.empty()) {
        const int K = pq.top().K;
        const ll num = pq.top().num;
        const int w = pq.top().w;
        pq.pop();
 
        seq.push_back({ K,num,w });
 
        if (!q.empty()) {
            pq.push({ K,q.front().first, q.front().second + w });
            q.pop();
        }
    }
 
    sort(seq.begin(), seq.end(), cmp2);
 
    for (ll i = 0; i < seq.size(); i++) {
        ans += seq[i].num * (i + 1);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
반응형

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

 

9879번: Cross Country Skiing

The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000. Some of the cells in this grid are designated as waypoints for the course. The org

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 좌표를 i * N + j를 통해 번호를 매겨줍니다.

 

2. 지도를 입력받고, 모든 노드들의 상하좌우로 인접한 노드들의 이어 차이값을 arr 배열에 저장합니다.

 

3. waypoint의 개수를 cnt에 저장합니다.

 

4. arr 배열을 D를 기준으로 오름차순으로 정렬합니다.

 

5. arr 배열을 for문을 통해 돌면서 이어주고, 부모노드가 waypoint 라면  cnt--를 해주고, D의 최댓값을 ans에 저장합니다.

 

6. cnt == 0이라면 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
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
102
103
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int D;
};
 
bool cmp(node left, node right)
{
    return left.D < right.D;
}
 
int M, N;
int map[500][500];
vector<int> waypoint;
vector<node> arr;
int vect[250000];
int cnt = -1;
int dy[2] = { 1,0 };
int dx[2] = { 0,1 };
int ans;
 
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;
}
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            vect[i * N + j] = i * N + j;
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            scanf("%d", &num);
 
            if (num == 1) cnt++;
 
            waypoint.push_back(num);
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < 2; k++) {
                int ii = i + dy[k];
                int jj = j + dx[k];
 
                if (ii >= 0 && ii < M && jj >= 0 && jj < N) {
                    arr.push_back({ i * N + j, ii * N + jj, abs(map[i][j] - map[ii][jj]) });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        int pa = Find(next.a);
        int pb = Find(next.b);
        const int D = next.D;
 
        if (pa != pb) {
            if (waypoint[pa] == 1 && waypoint[pb] == 1) {
                cnt--;
            }
            else if (waypoint[pa] == 0 && waypoint[pb] == 1) {
                swap(pa, pb);
            }
 
            ans = max(ans, D);
 
            Union(pa, pb);
        }
 
        if (cnt == 0) {
            printf("%d", ans);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
반응형

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

 

2820번: 자동차 공장

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 초기 월급을 arr배열에 저장하고, 그래프를 list에 저장합니다.

 

2. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 st[ n ], en[ n ]에 저장하고, arr2[ st[ n ] ] = arr[ n ] 을 통해 초기화해 줍니다.

 

3. 초기 segmentTree를 만들 때 arr2를 기준으로 만듭니다.

 

4. 월급이 오르거나 내리면 느리게 갱신되는 세그먼트 트리를 이용하여 st[ i ] + 1부터 en[ i ]까지 월급을 더해줍니다.

 

5. segTree에서 해당 노드를 출력해 줍니다.

 

[ 소스코드 ]

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
unsigned int segTree[1050000];
unsigned int lazy[1050000];
vector<int> list[500001];
int st[500001];
int en[500001];
int arr[500001];
int arr2[500001];
int cnt;
 
void dfs(int num)
{
    st[num] = ++cnt;
    arr2[cnt] = arr[num];
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    en[num] = cnt;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr2[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, unsigned int diff)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        if (s == e) {
            segTree[node] += diff;
        }
        else {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || idx > e) return;
    if (s == e) {
        cout << segTree[node] << '\n';
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
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 >> arr[i];
        if (i != 1) {
            int p;
            cin >> p;
            list[p].push_back(i);
        }
    }
 
    dfs(1);
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M; i++) {
        char com;
        int a;
        cin >> com >> a;
 
        if (com == 'p') {
            unsigned int x;
            cin >> x;
 
            updateTree(1, 1, N, st[a] + 1, en[a], x);
        }
        else {
            getTree(1, 1, N, st[a]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
반응형

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

 

16404번: 주식회사 승범이네

첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 st[ n ], en[ n ]에 저장합니다.

 

2. 돈을 벌거나 잃으면 느리게 갱신되는 세그먼트 트리를 이용하여 st[ i ]부터 en[ i ]까지 더해줍니다.

 

3. segTree에서 해당 노드를 출력해줍니다.

 

[ 소스코드 ]

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
102
103
104
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
int st[100001];
int en[100001];
int segTree[262222];
int lazy[262222];
vector<int> list[100001];
int cnt;
 
void dfs(int num)
{
    st[num] = ++cnt;
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    en[num] = cnt;
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        if (s == e) {
            segTree[node] += diff;
        }
        else {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (e < idx || s > idx) return;
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        int p;
        scanf("%d", &p);
 
        if (p != -1) {
            list[p].push_back(i);
        }
    }
 
    dfs(1);
 
    for (int j = 0; j < M; j++) {
        int com, i;
        scanf("%d %d", &com, &i);
 
        if (com == 1) {
            int w;
            scanf("%d", &w);
 
            updateTree(1, 1, N, st[i], en[i], w);
        }
        else {
            getTree(1, 1, N, st[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09

+ Recent posts

티스토리툴바