백준 2243번 사탕상자

문제링크: https://www.acmicpc.net/problem/2243

사용한 알고리즘: 세그먼트 트리


 맛이 1~10^6개 주어지고 각 사탕의 개수가 주어집니다. 사탕은 최대 2*10^9 개 입니다. (long long을 써야하죠) 맛의 순위 별로 사탕을 쭉 늘어놓고 그 중 i번째로 맛있는 사탕을 줄건데 그 사탕이 무슨 맛인지 출력하는 문제였습니다.
 이는 세그먼트 트리를 짤 수 있는지를 묻는 문제였습니다.

문제 풀이과정은 다음과 같습니다.
(1) 세그트리를 만들기 위해 배열을 만듭니다. 세그트리는 무조건 2^n 꼴로 동작합니다. 사탕의 맛이 10^6개 이므로 넉넉잡아 MAX = 2^20 개 잡았습니다. 세그트리를 만들기 위해 MAX 의 2배를 배열로 만들었습니다. 세그트리에는 1~MAX 맛의 사탕수들의 합을 쌓아 올릴 것입니다. ( candy[1] 에는 모든 사탕의 개수가 쌓여 있겠죠! )

(2) A=2로 입력이 주어지는경우 일반 세그트리의 update와 똑같은 방식으로 update 해줍니다. index 1~MAX-1 까지 쌓아놓습니다. candy[i] = candy[2*i]+candy[2*i+1] 이며
 candy[MAX] ~ candy[2*MAX-1] 는(사실 MAX+10^6-1 까지만 씁니다...) 각 1~10^6 의 맛들의 개수가 들어있는 index입니다.
 쉽게 사탕이 8개 있는 예를 들겠습니다. 사탕이 8개면 배열은 그 2배인 16개가 필요합니다.
1~8번 사탕 개수는 각각 candy[8] ~ candy[15] 에 들어있습니다. 이후 candy[1]~candy[15]를 쌓아 줄 것입니다. candy[4] = candy[8]+candy[9] 입니다. 즉 8번 맛의 사탕수와 9번맛의 사탕수의 합이 저장됩니다. candy[2] = candy[4]+candy[5] 입니다. 8번,9번 사탕수가 candy[4]에, 10번,11번 사탕수가 candy[5] 에 저장되어있으므로 candy[2] 는 8,9,10,11 사탕수의 합이 저장됩니다.

(3) A=1로 입력이 주어지는 경우 꺼내고자 하는 사탕위 순위 B 를 기준으로 만들어진 세그트리를 따라 갑니다. index=1 에서 부터 시작하며, 하위 index에 저장된 사탕수와 순위 B 를 비교합니다. 즉 candy[1] = candy[2] + candy[3] 에서 순위 B 보다 candy[2]가 크거나 같으면 index=2를 따라 재귀적으로 가고, 그렇지 않으면 candy[3]을 따라 가되, B의 순위 - candy[2] 가 새로운 순위가 됩니다. (candy[3] 에 저장된 맛들 앞에 candy[2]에 저장된 맛들이 있을 것이므로 candy[2] 에 저장된 맛들의 개수만큼 순위에서 빼주고 남은 순위를 candy[3]에서 찾아주면 됩니다.)


굉장히 설명을 못한 것 같지만.... 찰떡같이 이해 되셨기를 빌겠습니다... ㅎㅎ...

	#include <bits/stdc++.h>
	using namespace std;
	const long long MAX = 1LL<<20; // 2^20
	// index 잘 맞춰주는게 중요...!!
	int n;
	long long candy[1<<21];
	void update(long long i, long long val){
	i += MAX-1;
	candy[i] += val;
	while(i>1LL){
	i/=2;
	candy[i] = candy[i*2]+candy[i*2+1];
	}
	}
	long long search(long long ranking, long long idx){
	if(idx>=MAX){
	// 하나 빼먹었으니 빼줘
	update(idx-MAX+1,-1);
	return idx-MAX+1;
	}
	if(ranking<=candy[2*idx]) return search(ranking,idx*2);
	else return search(ranking-candy[2*idx],idx*2+1);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; ++i){
	long long a, b, c;
	cin >> a;
	if(a==1){
	cin >> b;
	cout << search(b,1) << '\n';
	}
	else{
	cin >> b >> c;
	update(b,c);
	}
	}
	return 0;

view raw BOJ 2243.cpp hosted with ❤ by GitHub