BOJ 2243 사탕상자

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

2243번: 사탕상자

 

solved의 class 6에 속해있는 문제이다.

생각보다 금방 풀려서 난이도 기여를 해볼까 했는데 스탠다드였다.

플레5 치고는 쉽게 풀리는 문제이니 도전해보면 좋을 듯 하다.

 

문제를 딱 읽어보면 이분탐색이라는 느낌이 확 온다.

현재 보유하고 있는 사탕중 n번째로 맛있는 사탕을 꺼내면 되기 때문이다.

하지만 문제는 보유하고 있는 사탕의 현황이 계속 바뀐다.

따라서 사탕의 현황이 변할때마다 update를 하게 되면 시간초과가 날 수밖에 없다.

 

그렇다면 어떻게 해야할까?

맛의 정도가 1부터 100만으로 고정이 되어있다는 것이 힌트다.

미리 1부터 100만까지의 칸을 만들어놓고, 특정 맛이 업데이트되면 해당 맛에 해당하는 칸에 개수를 업데이트 해주면 된다.

그리고 구간합!!을 구해놓으면, 현재 보고있는 구간에 몇개의 사탕이 있는지 알 수 있다.

현재 보고있는 구간에 몇개의 사탕이 있는지 알고 있으면, 이분탐색을 바로 적용할 수 있다.

그러면 무엇을 해야겠는가? 바로 세그트리를 빌드하면 된다.

 

우선 개수를 이용해 세그트리를 빌드해보자.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;

vector<int> cntseg;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int k = 1; 
	while (k < 1000000) k *= 2;
	k *= 2;
	cntseg.resize(k);

	int n; cin >> n;
	while (n--) {
		int a; cin >> a;
        
		//사탕을 꺼내는 경우
		if (a == 1) {
			int b; cin >> b;
            
			//세그트리의 루트부터 확인해보자.
			int idx = 1;
			while (b > 0) {
            	
				// 현재 보고있는 구간의 사탕의 개수와, 내가 찾으려는 사탕의 등수가 같으면 바로 종료
				if (b == cntseg[idx]) break;
                
  				// 리프노드에 도달해도 종료
				if (idx >= k / 2) break;
                
				// 만약 왼쪽구간의 사탕의 개수보다, 내가 찾으려는 사탕의 등수가 작거나 같다면, 왼쪽자식으로 이동
				if (b <= cntseg[idx * 2]) idx *= 2;
                
				// 만약 왼쪽구간의 사탕의 개수보다, 내가 찾으려는 사탕의 등수가 높다면 오른쪽으로 이동
				else { b -= cntseg[idx * 2]; idx = idx * 2 + 1; }
			}
            
            /* 
             idx를 이용해서 찾고 있는 사탕의 맛만 구현하면 된다.
			*/
            
            cntseg[t] -= 1;
			t /= 2;
			while (t > 0) {
				cntseg[t] = cntseg[t * 2] + cntseg[t * 2 + 1];
				t /= 2;
			}
		}
		else {
        	// 단순한 구간합 세그트리 빌드
			int b, c;
			cin >> b >> c;
			cntseg[k / 2 + b] += c;
			int t = (k / 2 + b)/2;
			while (t > 0) {
				cntseg[t] = cntseg[t * 2] + cntseg[t * 2 + 1];
				t /= 2;
			}
		}
	}
	return 0;
}

 

 

a = 1 인 경우의 while문이 제일 중요한 로직인데, 

분할정복을 생각해보면 왼쪽 자식과, 오른쪽 자식 중 누구를 선택해가면서 범위를 좁혀야 하는지 금방 생각해 낼 수 있다.

 

 

break문을 통해서 while문이 종료가 되면, idx값을 이용해서 내가 찾으려는 맛을 알아낼 수 있게 더 구현하면 된다.

( while문의 b > 0 조건을 통해 종료되는 경우는 존재하지 않는다. if문의 조건을 가지고 잘 생각해보면 알 수 있다.)

( 생각해보니 왜 저렇게 조건을 넣어놨는지 모르겠다. 머쓱)

 

이 while문이 종료가 되는 경우를 잘 생각해보자.

우선 쉬운 두번째 break문부터 보자.

바로 리프노드에 도달하면 종료. 이 경우에는 해당 노드가 가리키는 맛이 답이다.

그런데 첫번째 break문을 보면, 해당 구간에서의 사탕의 개수와, 내가 찾으려는 사탕의 등수가 같으면 종료이다.

이 말의 뜻은 무엇일까???

 

바로 해당 구간에서 제일! 맛이 없는 사탕이 답이라는 뜻이다.

그러면 어떻게 해야겠는가?

바로 구간에서 제일 맛이없는 사탕을 세그트리로 빌드하면 된다.

그러니까, 대충 seg[i] = seg[i*2+1] 이 default인데, seg[i*2+1]에 해당하는 맛이 없으면 seg[i*2]를 가져와야 한다는 뜻이다.

그러니, 해당 맛이 존재하는지 여부도 확인해야 하므로 개수까지 같이 세그트리로 빌드하면 된다.

나의 경우는 pair<int, int> (맛, 개수) 로 빌드했다.

 

 

아래는 완성된 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
vector<ii> seg;
vector<int> cntseg;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int k = 1; 
	while (k < 1000000) k *= 2;
	k *= 2;
	seg.resize(k);
	cntseg.resize(k);
	for (int i = k / 2; i < k; i++) {
		seg[i] = ii(i - k / 2, 0);
	}

	int n; cin >> n;
	while (n--) {
		int a; cin >> a;
		if (a == 1) {
			int b; cin >> b;
			int idx = 1;
			while (b > 0) {
				if (b == cntseg[idx]) break;
				if (idx >= k / 2) break;
				if (b <= cntseg[idx * 2]) idx *= 2;
				else { b -= cntseg[idx * 2]; idx = idx * 2 + 1; }
			}
			cout << seg[idx].first << "\n";
			int t = seg[idx].first + k / 2;
			cntseg[t] -= 1;
			t /= 2;
			while (t > 0) {
				cntseg[t] = cntseg[t * 2] + cntseg[t * 2 + 1];
				t /= 2;
			}
			t = seg[idx].first + k / 2;
			seg[t].second -= 1;
			t /= 2;
			while (t > 0) {
				if (seg[t * 2 + 1].second == 0) {
					seg[t] = seg[t * 2];
				}
				else {
					seg[t] = seg[t * 2 + 1];
				}
				t /= 2;
			}
		}
		else {
			int b, c;
			cin >> b >> c;
			cntseg[k / 2 + b] += c;
			int t = (k / 2 + b)/2;
			while (t > 0) {
				cntseg[t] = cntseg[t * 2] + cntseg[t * 2 + 1];
				t /= 2;
			}
			seg[k / 2 + b].second += c;
			t = (k / 2 + b) / 2;
			while (t > 0) {
				if (seg[t * 2 + 1].second == 0) {
					seg[t] = seg[t * 2];
				}
				else {
					seg[t] = seg[t * 2 + 1];
				}
				t /= 2;
			}
		}
	}
	return 0;
}

 

(맛, 개수) 로 구성된 세그트리도 하나하나 업데이트 해주는것을 잊지 말자!