반응형

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

 

5676번: 음주 코딩

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 구간 곱을 return 합니다.

 

2. 구간 곱의 부호만 판단하면 되므로 입력받은 값이 양수이면 1, 음수이면 -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
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>
#include<cstring>
#include<vector>
 
using namespace std;
 
int N, K;
int arr[100001];
int segTree[263000];
vector<char>ans;
 
int invert(int num)
{
    if (num > 0) return 1;
    else if (num < 0) return -1;
    return 0;
}
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = left * right;
}
 
int changeTree(int node, int start, int end, int idx, int V)
{
    if (idx < start || end < idx) return segTree[node];
    if (start == end) return segTree[node] = V;
 
    int mid = (start + end) / 2;
    int left = changeTree(node * 2, start, mid, idx, V);
    int right = changeTree(node * 2 + 1, mid + 1, end, idx, V);
 
    return segTree[node] = left * right;
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) return 1;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left * right;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> N >> K) {
        memset(segTree, 0, sizeof(segTree));
        ans.clear();
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            arr[i] = invert(arr[i]);
        }
 
        makeTree(1, 1, N);
 
        for (int k = 0; k < K; k++) {
            char ch;
            cin >> ch;
 
            if (ch == 'C') {
                int i, V;
                cin >> i >> V;
 
                V = invert(V);
                changeTree(1, 1, N, i, V);
                arr[i] = V;
            }
            else {
                int i, j;
                cin >> i >> j;
 
                int temp = getTree(1, 1, N, i, j);
 
                if (temp < 0) ans.push_back('-');
                else if (temp > 0) ans.push_back('+');
                else ans.push_back('0');
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i];
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
반응형

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

 

18436번: 수열과 쿼리 37

길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 짝수와 홀수의 개수를 구해야 하므로 각 노드별로 짝수의 개수와 홀수의 개수를 저장해 return 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int, int> segTree[263000];
int arr[100001];
 
pair<int, int> makeTree(int node, int start, int end)
{
    if (start == end) {
        if (arr[start] % 2 == 0) {
            return segTree[node] = { 0,1 };
        }
        else {
            return segTree[node] = { 1,0 };
        }
    }
 
    int mid = (start + end) / 2;
    pair<int, int> left = makeTree(node * 2, start, mid);
    pair<int, int> right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = { left.first + right.first, left.second + right.second };
}
 
void modifyTree(int node, int start, int end, int idx, int odd, int even)
{
    if (idx < start || end < idx) return;
 
    segTree[node].first += odd;
    segTree[node].second += even;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, idx, odd, even);
        modifyTree(node * 2 + 1, mid + 1, end, idx, odd, even);
    }
}
 
int oddTree(int node, int start, int end, int sidx, int eidx)
{
    if (eidx < start || sidx > end) return 0;
    if (sidx <= start && end <= eidx) return segTree[node].first;
 
    int mid = (start + end) / 2;
    int left = oddTree(node * 2, start, mid, sidx, eidx);
    int right = oddTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int evenTree(int node, int start, int end, int sidx, int eidx)
{
    if (eidx < start || sidx > end) return 0;
    if (sidx <= start && end <= eidx) return segTree[node].second;
 
    int mid = (start + end) / 2;
    int left = evenTree(node * 2, start, mid, sidx, eidx);
    int right = evenTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int n, l, r;
        scanf("%d %d %d", &n, &l, &r);
 
        if (n == 1) {
            if (arr[l] % 2 == 0 && r % 2 != 0) {
                modifyTree(1, 1, N, l, 1, -1);
            }
            else if (arr[l] % 2 != 0 && r % 2 == 0) {
                modifyTree(1, 1, N, l, -1, 1);
            }
 
            arr[l] = r;
        }
        else if (n == 2) {
            printf("%d\n", evenTree(1, 1, N, l, r));
        }
        else {
            printf("%d\n", oddTree(1, 1, N, l, r));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
반응형

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

 

14427번: 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값의 index를 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값의 index return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100001];
pair<int, int> segTree[263000];
 
pair<int, int> makeTree(int node, int start, int end)
{
    if (start == end)return segTree[node] = { arr[start], start };
 
    int mid = (start + end) / 2;
    pair<int, int> left = makeTree(node * 2, start, mid);
    pair<int, int> right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (left <= right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
pair<int, int> modifyTree(int node, int start, int end, int i, int v)
{
    if (i < start || end < i) return segTree[node];
    if (start == end) return segTree[node] = { arr[start], start };
 
    int mid = (start + end) / 2;
    pair<int, int> left = modifyTree(node * 2, start, mid, i, v);
    pair<int, int> right = modifyTree(node * 2 + 1, mid + 1, end, i, v);
 
    if (left <= right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int n;
        scanf("%d", &n);
 
        if (n == 1) {
            int i, v;
            scanf("%d %d", &i, &v);
            arr[i] = v;
 
            modifyTree(1, 1, N, i, v);
        }
        else {
            printf("%d\n", segTree[1].second);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
반응형

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

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack<pair<int, int>> s를 만들어 타워의 인덱스와 높이를 저장합니다.

 

2. 타워의 높이를 입력받고, s.top()보다 타워의 높이가 더 크다면 (s.top() < h) s.pop()을 해줍니다. 왜냐하면 s.top()의 타워는 뒤의 타워가 더 크므로 더 이상 레이저를 수신할 수 없기 때문입니다.

 

3. s.top()보다 타워의 높이가 더 작다면 현재 s.top()의 인덱스를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
 
int main()
{
    stack<pair<int,int>> s;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        int h;
        scanf("%d", &h);
 
        while (!s.empty()) {
            if (s.top().second > h) {
                printf("%d ", s.top().first);
                break;
            }
            s.pop();
        }
 
        if (s.empty()) {
            printf("0 ");
        }
 
        s.push({ i,h });
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
반응형

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

 

13975번: 파일 합치기 3

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수를 입력받을 때 priority_queue에 오름차순으로 넣습니다.

 

2. pq에서 맨 앞의 두 수를 뽑아 더한 값을 ans에 더하고, 그 값을 다시 pq에 넣습니다.

 

3. pq가 빌 때까지 위 과정을 반복합니다.

 

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
#include<iostream>
#include<queue>
#define ll long long
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int K;
        scanf("%d", &K);
 
        priority_queue<ll, vector<ll>, greater<ll>> pq;
 
        ll ans = 0;
 
        for (int i = 0; i < K; i++) {
            ll num;
            scanf("%lld", &num);
 
            pq.push(num);
        }
 
        while (1) {
            const ll a = pq.top();
            pq.pop();
            const ll b = pq.top();
            pq.pop();
 
            ans += a + b;
 
            if (pq.empty()) break;
 
            pq.push(a + b);
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
반응형

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

 

16562번: 친구비

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 친구비를 입력받고, 이 값을 priority_queue에 친구비와 친구의 번호를 넣습니다.

 

2. 이미 친구인 번호를 입력받고, 이를 Union-Find를 통해 연결 관계를 저장합니다.

 

3. 나와 친구가 되면 0과 연결하고, 친구가 될 때 친구비를 ans에 저장합니다.

 

4. 총 친구비 ans가 k를 넘어서면 Oh no를 출력하고, 그렇지 않다면 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M, k;
int arr[10001];
int vect[10001];
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &k);
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        pq.push({ arr[i], i });
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int v, w;
        scanf("%d %d", &v, &w);
        if (Find(v) != Find(w)) {
            Union(v, w);
        }
    }
 
    int ans = 0;
 
    while (!pq.empty()) {
        const int cost = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (Find(cur) != 0) {
            Union(0, cur);
            ans += cost;
        }
    }
 
    if (ans > k) {
        printf("Oh no");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
반응형

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

 

1275번: 커피숍2

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합의 크기가 int 범위를 벗어나므로 long long 자료형을 사용해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q;
ll arr[100001];
ll segTree[263000];
 
ll makeTree(ll node, ll start, ll end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    ll left = makeTree(node * 2, start, mid);
    ll right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = right + left;
}
 
void modifyTree(ll node, ll start, ll end, ll a, ll diff)
{
    if (a < start || a > end) return;
    segTree[node] += diff;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, a, diff);
        modifyTree(node * 2 + 1, mid + 1, end, a, diff);
    }
}
 
ll sumTree(ll node, ll start, ll end, ll x, ll y)
{
    if (y < start || x > end) return 0;
    if (x <= start && end <= y) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sumTree(node * 2, start, mid, x, y);
    ll right = sumTree(node * 2 + 1, mid + 1, end, x, y);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1,1,N);
 
    for (int i = 0; i < Q; i++) {
        ll x, y, a, b;
        scanf("%lld %lld %lld %lld", &x, &y, &a, &b);
        if (y < x) {
            ll temp = x;
            x = y;
            y = temp;
        }
        ll diff = b - arr[a];
        arr[a] = b;
        printf("%lld\n", sumTree(1, 1, N, x, y));
        modifyTree(1, 1, N, a, diff);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
반응형

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

 

10868번: 최솟값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값을 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값을 return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100001];
int segTree[263000];
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (left < right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 1987654321;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left < right) {
        return left;
    }
    else {
        return right;
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", getTree(1, 1, N, a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
반응형

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

 

14438번: 수열과 쿼리 17

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값을 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값을 return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int segTree[263000];
int arr[100001];
int N, M;
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (right < left) {
        segTree[node] = right;
        return right;
    }
    else {
        segTree[node] = left;
        return left;
    }
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) return 1987654321;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left < right) {
        return left;
    }
    else {
        return right;
    }
}
 
int modifyTree(int node, int start, int end, int idx, int v)
{
    if (idx > end || idx < start) return segTree[node];
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = modifyTree(node * 2, start, mid, idx, v);
    int right = modifyTree(node * 2 + 1, mid + 1, end, idx, v);
 
    if (left < right) {
        segTree[node] = left;
        return left;
    }
    else {
        segTree[node] = right;
        return right;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int n;
        scanf("%d", &n);
 
        if (n == 1) {
            int i, v;
            scanf("%d %d", &i, &v);
            arr[i] = v;
            modifyTree(1, 1, N, i, v);
        }
        else {
            int i, j;
            scanf("%d %d", &i, &j);
            printf("%d\n", getTree(1, 1, N, i, j));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
반응형

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

 

12837번: 가계부 (Hard)

살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 총합이 int형 범위를 벗어나므로 long long형으로 저장합니다.

 

[ 소스코드 ]

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, Q;
ll segTree[2100000];
 
ll sumTree(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sumTree(node * 2, start, mid, sidx, eidx);
    ll right = sumTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
void modifyTree(int node, int start, int end, int idx, ll x)
{
    if (idx < start || idx > end) return;
    segTree[node] += x;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, idx, x);
        modifyTree(node * 2 + 1, mid + 1, end, idx, x);
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 0; i < Q; i++) {
        int n, p, q;
        scanf("%d %d %d", &n, &p, &q);
 
        if (n == 1) {
            modifyTree(1, 1, N, p, q);
        }
        else {
            printf("%lld\n", sumTree(1, 1, N, p, q));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29

+ Recent posts

티스토리툴바