Henu
개발냥발
Henu
전체 방문자
오늘
어제
  • 분류 전체보기 (411)
    • DevOps (52)
      • Kubernetes (19)
      • Docker (14)
      • AWS (3)
      • Nginx (4)
      • Linux (4)
      • ArgoCD (1)
      • CN (2)
      • NATS (0)
      • Git (5)
    • Back-End (30)
      • Django (18)
      • Spring (5)
      • JPA (1)
      • MSA (5)
    • CS (87)
      • SystemSoftware (20)
      • OS (25)
      • Computer Architecture (16)
      • Network (23)
      • Database (2)
    • Lang (21)
      • Java (9)
      • Python (4)
      • C# (8)
    • Life (12)
    • 블록체인 (2)
    • Algorithm (204)
      • BOJ (160)
      • 프로그래머스 (19)
      • LeetCode (4)
      • SWEA (1)
      • 알고리즘 문제 해결 전략 (8)
      • DS, algorithms (7)
      • Checkio (5)
    • IT (2)

블로그 메뉴

  • GitHub
  • 글쓰기
  • 관리자

공지사항

  • Free!

인기 글

태그

  • 다이나믹 프로그래밍
  • 프로그래머스
  • django
  • BFS
  • DFS
  • Kubernetes
  • boj
  • docker
  • Network
  • 백트래킹

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Henu

개발냥발

[백준 2243] 사탕상자 (C++)
Algorithm/BOJ

[백준 2243] 사탕상자 (C++)

2021. 8. 3. 19:13
 

2243번: 사탕상자

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

www.acmicpc.net

세그먼트 트리


이 문제는 array값이 주어지지 않는다.

 

그럼 트리를 어떻게 만드는가?

사탕의 맛이 1부터 1,000,000 까지의 정수로 표현된다고 한다.

그래서 사탕의 맛을 트리의 인덱스(구간)로 설정하면 되고 사탕의 맛의 개수를 트리의 값으로 설정하면 풀 수 있다.

 

 

 

[백준 1321] 군인 C++

1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄

hyeo-noo.tistory.com

 

트리 모델링을 했다면 위 문제와 비슷하게 풀면 된다.

 

사탕을 입력할 때는 입력받은 사탕의 맛(트리의 구간(인덱스))이 존재하는 구간에 입력하는 개수만큼 재귀적으로 더해준다.

사탕을 꺼낼 때는 자식 노드의 값(구간의 사탕의 개수)을 통해 재귀 탐색할 위치를 정해준다.

찾고자 하는 사탕의 순위가 왼쪽 트리의 값(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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 1000001
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N;
int tree[MAX * 4];
 
int make_tree(int startidx, int endidx, int node){
    if(startidx == endidx) return tree[node] = 0;
    int mid = (startidx + endidx) / 2;
    return tree[node] = make_tree(startidx, mid, node*2) + make_tree(mid+1, endidx, node*2+1);
}
 
// A : 2 -> 사탕 넣는 경우
void update(int startidx, int endidx, int node, int flavornum, int up){
    if(flavornum < startidx || flavornum > endidx) return;
    tree[node] += up;
    if(startidx == endidx) return;
    int mid = (startidx + endidx) / 2;
    update(startidx, mid, node*2, flavornum, up);
    update(mid+1, endidx, node*2+1, flavornum, up);
}
 
// A : 1 -> targetnum 순위의 사탕 꺼냄
void getQuery(int startidx, int endidx, int node, int targetnum){
    if(startidx == endidx){
        cout << startidx << "\n";
        tree[node]--;
        return;
    }
    int leftnum = tree[node*2];
    int mid = (startidx + endidx) / 2;
    
    if(targetnum <= leftnum) getQuery(startidx, mid, node*2, targetnum);
    else getQuery(mid+1, endidx, node*2+1, targetnum - leftnum);
    
    tree[node]--;
}
 
void solve(){
    cin >> N;
    int A, B, C;
    for(int i = 0; i < N; i++){
        cin >> A;
        if(A == 1){
            cin >> B;
            getQuery(1, MAX, 1, B);
        }
        else{
            cin >> B >> C;
            update(1, MAX, 1, B, C);
        }
    }
}
 
int main(){
    fastio
    solve();
    
    return 0;
}
 
Colored by Color Scripter
cs

 

'Algorithm > BOJ' 카테고리의 다른 글

[백준 14284] 간선 이어가기 2 (C++)  (0) 2021.08.04
[백준 14391] 종이 조각 (C++)  (2) 2021.08.04
[백준 13308] 주유소 (C++)  (0) 2021.08.02
[백준 11377] 열혈강호 3 (C++)  (0) 2021.08.02
[백준 2159] 케익 배달 (C++)  (0) 2021.08.01
    'Algorithm/BOJ' 카테고리의 다른 글
    • [백준 14284] 간선 이어가기 2 (C++)
    • [백준 14391] 종이 조각 (C++)
    • [백준 13308] 주유소 (C++)
    • [백준 11377] 열혈강호 3 (C++)

    티스토리툴바