[3일차] 자료구조 N - 2243: 사탕상자

플래티넘 Ⅴ

 

#include <iostream>
using namespace std;

int baseNum = 1048576;
int IDT[3000000] = { 0, };
int n;

int findKth(int K) {

	int idx = 1;

	//리프 노드 도착하면 탈출
	while (idx < baseNum) {
		int lc = 2 * idx;
		int rc = 2 * idx + 1;
		if (IDT[lc] >= K) {
			//lc로 이동
			idx = lc;
		}
		else {
			//rc로 이동
			idx = rc;
			K -= IDT[lc];
		}
	}
	return idx - baseNum + 1;
}

void updateTree(int idx, int newNum) {
	IDT[idx] = newNum;

	while (idx /= 2) {
		int lci = idx * 2;
		int rci = lci + 1;
		IDT[idx] = IDT[lci];
		IDT[idx] += IDT[rci];
	}
}

int main() {
	scanf("%d", &n);

	//(트리 초기화 필요없음 어차피 처음엔 다 0개)

	int a, b, c;
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a, &b);

		int candyLevel;
		//b 순위의 사탕 꺼내기
		if (a == 1) {
			candyLevel = findKth(b);
			printf("%d\n", candyLevel);
			updateTree(candyLevel - 1 + baseNum, IDT[candyLevel - 1 + baseNum] - 1);
		}
		else {//b맛의 사탕 c개수만큼 +넣거나 -빼기
			scanf("%d", &c);
			updateTree(b - 1 + baseNum, IDT[b - 1 + baseNum] + c);
		}

		//리프 출력해본거
		/*
		for (int j = baseNum; j < baseNum + n; j++) printf("%d ", IDT[j]);
		printf("\n");
		*/
	}
}

 

인덱스 트리(or 세그먼트 트리) 문제

 

진짜... 화난다~~!!

updateTree 부분에 rc가 범위를 벗어날까봐 원래 rc > baseNum + n 이면 rc를 더하지 않는 식으로

업데이트를 해줬는데 이 부분이 틀려가지고..

 

n이 아니라 1000000으로 해줘야 한다. 무조건 leaf 노드에 1000000개가 들어가니까..

웬 n?? 여기서 n은 사탕상자에 몇번 손을 넣냐.. 의 테스트 케이스 비슷한 개념이고

원래 풀던 인덱스 트리 문제에서 가져왔는데 거기가 n이 leaf노드에 들어가는 베이스 개수였어서 ㅠㅠ ㅇㄴ

 

암튼 헤매부렀다.. update랑 findKth 하는 부분 더 간단하게 쓸 수도 있는데

그냥 아직 초보니까.. 이해하기 쉬우라고 lc rc 놓고 했다

 

끝!