[BOJ/C++] 2243번 문제풀이

문제 설명

수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다.

각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.

수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 꺼낼 사탕을 골라내는 일은 매우 어렵다. 수정이를 도와주는 프로그램을 작성하시오.

입력

첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그러한 사탕의 개수이다. C가 양수일 경우에는 사탕을 넣는 경우이고, 음수일 경우에는 빼는 경우이다. 맨 처음에는 빈 사탕상자에서 시작한다고 가정하며, 사탕의 총 개수는 2,000,000,000을 넘지 않는다. 또한 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다. 

출력

A가 1인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다.

---

풀이 과정

이 문제는 아직까지도 이해가 안가는 문제이다.... 우선 코드는 구글링을 참고하여 가져와 봤지만 아직 내가 많이 부족하여 코드를 봐도 사실 잘 이해가 되지 않는다... 하지만 이해한만큼 풀이를 작성해보려고 한다.

 

문제를 요약하여 설명하면 다음과 같다.사탕상자에 사탕을 넣어 말을 잘 들을때 동생에게 사탕을 꺼내주려한다. 이때 1인 경우 b번째 순위의 사탕을 꺼내고 2인 경우 b맛인 사탕 c개를 넣는다. c는 음수가 될수도 있으며 그 경우 빼준다.

 

해당 문제는 다음과 같은 과정으로 접근할 수 있다.

• 세그트리의 인덱스를 사탕의 맛이라고 두고, 값을 사탕의 개수로 둔다.
• 세그합을 구현하고, query를 통해 해당하는 순위의 알맞은 맛의 사탕을 구한다.
• 부모노드 입장에서 왼쪽노드냐, 오른쪽 노드냐를 판단하는 건 왼쪽 노드 세그 구간합이 target 보다 작거나 같은 경우 왼쪽, 반대의 경우 오른쪽으로 가면 된다. 단, 오른쪽으로 갈 경우 해당 트리에 대해 순위를 판단하기 때문에 target-tree[index*2]; 값이 넘겨질 것이다.

 

이 문제는 세그먼트 트리에 대한 이해가 필요할 것 같으므로 세그먼트 트리에 대해 간단하게 알아보자.

세그먼트 트리 (Segment Tree)

• 여러 개의 데이터가 존재할 때 특정 구간의 합을 구하는데 사용하는 자료구조
• 트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다.

[세그먼트 관련 참고 자료]

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree

 

세그먼트 트리에 관한 내용 외에도 세그먼트 트리를 해당 문제에 적용하여 설명된 링크를 아래에 첨부해놓고 같이 읽어보면 좋을 것 같다.

 

[세그먼트 트리 내용 적용한 풀이]

https://velog.io/@solser12/%EB%B0%B1%EC%A4%80-2243-%EC%82%AC%ED%83%95%EC%83%81%EC%9E%90-JAVA

 

 

세그먼트와 관련된 내용을 참고하여 코드를 작성할 수 있다. 여기서 query의 경우에는 자식 노드의 값과 target 값을 통해 왼쪽으로 갈지 오른쪽으로 갈지 정한다. 이 문제는 코드를 내 힘으로 작성하지 못했지만 다음에 기회가 될 때, 세그먼트 트리와 관련된 문제들을 여러개 풀어보면서 해당 자료구조에 익숙해지고 싶다..

#include <iostream>
using namespace std;
const int MAXN = 1000001;

int n;
int tree[MAXN * 4];

// 쿼리합 갱신
void update(int index, int target, int diff, int start, int end) {
	if (target < start || target > end)
		return;
	tree[index] += diff;
	if (start == end)
		return;
	int mid = (start + end) / 2;
	update(index * 2, target, diff, start, mid);
	update(index * 2 + 1, target, diff, mid + 1, end);
}

// 순위 얻는 쿼리
int query(int index, int target, int start, int end) {
	if (start == end)
		return start;
	int mid = (start + end) / 2;
	if (target <= tree[index * 2])
		return query(index * 2, target, start, mid);
	else
		return query(index * 2 + 1, target - tree[index*2], mid + 1, end);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	while (n--) {
		int a, b, c;
		cin >> a;
        
		// B순위 사탕을 꺼내는 경우
		if (a == 1) {
			cin >> b;
			int favor = query(1, b, 1, MAXN);
			cout << favor << '\n';
			update(1, favor, -1, 1, MAXN);
		}
        
		// B맛의 C개의 사탕을 넣는 경우(음수인경우는 뺀다)
		else {
			cin >> b >> c;
			update(1, b, c, 1, MAXN);
		}
	}
	return 0;
}

 

 

[참고자료]

https://ghdic.github.io/ps/boj-2243/