[BOJ/백준 2243/C++] 사탕상자
https://www.acmicpc.net/problem/2243
2243번: 사탕상자
첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이
www.acmicpc.net
[문제 요약]
- 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다.
- 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다.
- 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.
- 수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 꺼낼 사탕을 골라내는 일은 매우 어렵다. 수정이를 도와주는 프로그램을 작성하시오.
- A가 1인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다.
[문제 조건]
- 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다.
- 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다.
- A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다.
- 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그러한 사탕의 개수이다.
- C가 양수일 경우에는 사탕을 넣는 경우이고, 음수일 경우에는 빼는 경우이다.
- 맨 처음에는 빈 사탕상자에서 시작한다고 가정하며, 사탕의 총 개수는 2,000,000,000을 넘지 않는다. 또한 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다.
- 시간 제한 : 2초
- 메모리 제한 : 128MB
[문제 풀이]
이번 문제는 세그먼트 트리의 이용해서 풀 수 있다.
세그먼트 트리의 리프노드를 제외한 다른 모든 노드들은 해당하는 구간에 존재하는 사탕의 개수로 생각하고 풀 수 있다.
리프노드는 각 번호에 해당하는 사탕의 개수로 생각하면 된다.
사탕 삽입
void insert(int start, int end, int node, int idx, int cnt)
{
if (idx < start || idx > end) return;
if (idx == start && end == idx)
{
seg_tree[node] += cnt;
return;
}
int mid = (start + end) / 2;
insert(start, mid, node * 2, idx, cnt);
insert(mid + 1, end, node * 2 + 1, idx, cnt);
seg_tree[node] = seg_tree[node * 2] + seg_tree[node * 2 + 1];
}리프노드를 확인할때 추가할 개수만큼 증가시켜주면 된다.
사탕 번호 출력
사탕 번호 출력은 입력으로 들어온 순위의 사탕을 출력을 해주면 된다.
세그먼트 트리를 이용해서 어떻게 출력할 수 있을까?
잘 생각해보면 우리가 구성한 세그먼트 트리는 다음과 같다.
- 해당 노드가 담당하는 구간이 0~11이라고 가정하면 (사탕번호와 1차이가 나게 설정) 1번 사탕~12번 사탕의 개수를 의미한다.
예를들어 우리가 찾고자 하는 순위가 x번째 사탕이라고 생각한다면, 현재노드의 왼쪽자식의 사탕 개수가 x보다 작을 경우 우리가 찾는 사탕은 오른쪽 노드에 있을 것이다. 반대로 왼쪽 자식의 사탕의 개수가 x보다 많다면 우리가 찾는 사탕은 왼쪽에 존재할 것이다.
이 아이디어를 이용해 x번째 사탕을 찾을 수 있다.
void find(int start, int end, int node, int rank)
{
if (start == end)
{
seg_tree[node]--;
cout << start + 1 << "\n";
return;
}
int mid = (start + end) / 2;
if (seg_tree[node * 2] >= rank)
{
find(start, mid, node * 2, rank);
}
else
find(mid+1, end, node * 2 + 1, rank - seg_tree[node*2]);
seg_tree[node] = seg_tree[node * 2] + seg_tree[node * 2 + 1];
}
[전체 소스 코드]
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define INF 987654321
#define mod 1000000
#define pii pair<int,int>
#define MAX 1000000
using namespace std;
vector<long long> seg_tree;
vector<long long> dt;
int n;
void insert(int start, int end, int node, int idx, int cnt)
{
if (idx < start || idx > end) return;
if (idx == start && end == idx)
{
seg_tree[node] += cnt;
return;
}
int mid = (start + end) / 2;
insert(start, mid, node * 2, idx, cnt);
insert(mid + 1, end, node * 2 + 1, idx, cnt);
seg_tree[node] = seg_tree[node * 2] + seg_tree[node * 2 + 1];
}
void find(int start, int end, int node, int rank)
{
if (start == end)
{
seg_tree[node]--;
cout << start + 1 << "\n";
return;
}
int mid = (start + end) / 2;
if (seg_tree[node * 2] >= rank)
{
find(start, mid, node * 2, rank);
}
else
find(mid+1, end, node * 2 + 1, rank - seg_tree[node*2]);
seg_tree[node] = seg_tree[node * 2] + seg_tree[node * 2 + 1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
seg_tree.resize(MAX * 4);
cin >> n;
for (int i = 0; i < n; i++)
{
int type;
int A, B;
cin >> type;
if (type == 1)
{
cin >> A;
find(0, MAX - 1, 1, A);
}
//삽입
else
{
//A를 B개만큼
cin >> A >> B;
insert(0, MAX - 1, 1, A - 1, B);
}
}
}
굳