[백준] 사탕상자 2243 - JAVA

문제

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

2243번: 사탕상자

 

풀이

Index Tree 를 이용하여 푼다

 

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	static int n;
	static int arr [] = new int [3000000];
	static int first;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		first = 1;
		while(first<1000000) {
			first = first*2;
		}
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			
			if(a==1) {
				int b = Integer.parseInt(st.nextToken());
				getCandy(b);
				
			}
			else if(a==2) {
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				edit(b, c);
			}
		}
		
		System.out.print(sb);
	}
	
	
	static void edit(int pos, int cnt) {
		int idx = first + pos -1;
		
		arr[idx] += cnt;
		
		idx = idx/2;
		while(idx > 0) {
			arr[idx] = arr[idx*2]+ arr[idx*2+1];
			idx = idx/2;
		}
		
	}
	
	
	static void getCandy(int rank) {
		int idx = 1;
		
		while(idx<first) {
			if(arr[idx*2]>=rank) {
				idx = idx*2;
			}
			else {
				rank = rank - arr[idx*2];
				idx = idx*2 +1;
			}	
		}
		
		sb.append(idx - first + 1).append("\n");
		
		arr[idx] = arr[idx] - 1;;
		idx = idx/2;
		while(idx > 0) {
			arr[idx] = arr[idx*2]+ arr[idx*2+1];
			idx = idx/2;
		}

		
	}
}