반응형

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

 

2243번: 사탕상자

첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

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

 

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

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

rudalsd.tistory.com

 

각각의 노드들에는 왼쪽 자식 노드 값 + 오른쪽 자식 노드 값을 넣어줍니다. 노드의 값은 가지고 있는 사탕의 개수이고, 이를 활용해서 특정 idx에 무슨 맛의 사탕이 있는지 알아낼 수 있습니다.

 

오른쪽 노드로 내려갈 때는 오른쪽 노드의 사탕 개수만 가지고 때문에 왼쪽 노드의 사탕 개수는 포함되어 있지 않습니다.

 

따라서, 오른쪽 노드로 내려갈 때는 idx에서 왼쪽 노드의 값을 빼주는 방법을 이용하여 문제를 풀 수 있습니다.

 

[ 소스 코드 ]

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
#include<iostream>
 
using namespace std;
 
int n;
int segTree[2111111];
 
void update(int node, int start, int end, int taste, int N)    //사탕 숫자 update
{
    if (taste > end || taste < start) return;    //범위를 벗어나면
 
    segTree[node] += N;
 
    if (start == end) return;    //범위에 완전히 포함되면
 
    //범위에 일부 포함되면
    int mid = (start + end) / 2;
    update(node * 2, start, mid, taste, N);
    update(node * 2 + 1, mid + 1, end, taste, N);
}
 
int get(int node, int start, int end, int idx)    //idx번째 사탕의 맛 얻기
{
    if (start == end) {        //범위에 정확히 들어오면
        return start;
    }
 
    int mid = (start + end) / 2;
    if (segTree[node * 2] >= idx) return get(node * 2, start, mid, idx);    //왼쪽 자식 노드
    return get(node * 2 + 1, mid + 1, end, idx - segTree[node * 2]);        //오른쪽 자식 노드
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int A, B, C;
        scanf("%d", &A);
 
        if (A == 1) {        //사탕 꺼내기
            scanf("%d", &B);
            int idx = get(1, 1, 1000000, B);
            printf("%d\n", idx);
            update(1, 1, 1000000, idx, -1);
        }
        else {                //사탕 넣고, 빼기
            scanf("%d %d", &B, &C);
            update(1, 1, 1000000, B, C);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11725번 - 트리의 부모 찾기 (C++)  (0) 2022.07.31
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
[ 백준 ] 2618번 - 경찰차 (C++)  (0) 2022.07.26
[ 백준 ] 14938번 - 서강그라운드 (C++)  (0) 2022.07.25

+ Recent posts

티스토리툴바