백준 1321 c++ "군인" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리를 이용하여 몇번째 인지 구하는 문제이다.

이전 풀었떤 구슬 문제나 중앙값 문제 등등 모두 같은 계열의 문제이다.

늘 해오던 습관은 항상 세그먼트 배열 크기를 1000000*4인 형태로 초기화 하고

update 나 query등 start 와 end 의 범위를 1~ 1000000 으로 설정했는데

요번에는 start ==1 end ==N 으로 잡으니 오류가 났다.

그 이유는 트리를 처음 초기화 한 숫자 즉 1000000 에 쿼리나 update init 등등 맞혀야 된다는 말이다.

즉 end == 1000000 으로 해야된다 .

만약 tree초기화를 300*4 로 하게 되면 query 등등의 end 값은 300 으로 해야 된다.

 

Query에 원하는 지역으로 탐색하기 위해 자신의 왼쪽 자식노드보다 count숫자가 작으면 왼쪽 자식노드로 이동하고

반대면 오른쪽 자식노드로 이동한뒤 자신의 count 를 왼쪽 자신노드만큼 배면 쉽게 문제를 해결할 수 있다.

[코드 해설]

 

• 입력 데이터 초기화 (Input 함수)
  Input 함수는 배열 arr의 크기 N을 입력받고, 배열의 각 요소를 초기화한다.
• 세그먼트 트리 초기화 (Init_Tree 함수)
  Init_Tree 함수는 세그먼트 트리를 구성하는 역할을 한다.
  • 리프 노드에서 배열 arr의 값을 트리에 저장한다.
  • 내부 노드에서는 왼쪽 자식과 오른쪽 자식의 합을 저장한다.
• 세그먼트 트리 합 갱신 (sum_Tree 함수)
  sum_Tree 함수는 재귀적으로 자식 노드들의 합을 계산하여 부모 노드의 값을 갱신한다.
  • 리프 노드에서 더 이상 분할할 수 없을 때 재귀 호출을 종료한다.
• 특정 순위 값 찾기 (Query 함수)
  Query 함수는 입력받은 순위 count에 해당하는 값을 찾는 역할을 한다.
  • 세그먼트 트리를 탐색하며 왼쪽 자식의 합이 count 이상인 경우, 왼쪽 자식 노드로 이동한다.
  • 그렇지 않으면 오른쪽 자식 노드로 이동하며, count에서 왼쪽 자식의 합을 뺀 값을 기준으로 탐색한다.
  • 최종적으로 값이 위치한 리프 노드의 start 값을 ans에 저장한다.
• 세그먼트 트리 값 갱신 (Update 함수)
  Update 함수는 배열의 특정 값이 변경될 때 세그먼트 트리를 갱신한다.
  • 변경된 인덱스 idx가 포함된 범위를 찾아가며, 값의 차이 diff를 더하거나 뺀다.
  • 모든 관련 노드들의 값을 업데이트하여 트리의 일관성을 유지한다.
• 게임 로직 실행 (Game_Start 함수)
  Game_Start 함수는 프로그램의 주요 실행 로직을 담당한다.
  • 입력받은 명령어에 따라 업데이트(값 변경) 또는 쿼리(특정 순위 값 찾기)를 수행한다.
  • 명령어 1은 값 변경을 위한 Update 호출, 명령어 2는 특정 순위 값을 찾기 위한 Query 호출을 의미한다.
  • 쿼리 결과는 cout으로 출력된다.
• 메인 함수 (main 함수)
  main 함수는 입력 데이터를 초기화한 후, 게임 로직을 실행하는 Game_Start를 호출하여 프로그램의 흐름을 제어한다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<long> tree;
vector<long > arr;
long ans = 0;

void Input() {
	cin >> N;
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

}

void Init_Tree(int node, int start, int end) {
	if (start == end) {
		
			tree[node] = arr[start];
	
		return;
	}
	int mid = (start + end) / 2;
	
		Init_Tree(node * 2, start, mid);
	
		Init_Tree(node * 2 + 1, mid + 1, end);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void sum_Tree(int node, int start, int end) {
	if (start == end) {
		return;
	}

	int mid = (start + end) / 2;
	sum_Tree(node * 2, start, mid);
	sum_Tree(node * 2 + 1, mid + 1, end);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void Query(int node, int start, int end, int count) {
	if (start == end) {
		ans = start;
		return;
	}

	int mid = (start + end) / 2;
	if (tree[node * 2] >= count) {
		Query(node * 2, start, mid, count);
	}
	else {
		Query(node * 2 + 1, mid + 1, end, count - tree[node * 2]);
	}
}

void Update(int node, int start, int end, int idx, int diff) {
	if (start == end) {
		tree[node] += diff;
		return;
	}

	int mid = (start + end) / 2;
	if (mid >= idx) {
		Update(node * 2, start, mid, idx, diff);
	}
	else {
		Update(node * 2 + 1, mid + 1, end, idx, diff);
	}

	tree[node] += diff;
}

void Game_Start() {
	cin >> M;

	tree.resize(N * 4 + 1,0);

	
		Init_Tree(1, 1, N);
	
	

	for (int i = 0; i < M; i++) {
		int flag;
		cin >> flag;

		if (flag == 1) {
			int idx, diff;
			cin >> idx >> diff;
			Update(1, 1, N, idx, diff);
		}
		else {
			int num;
			cin >> num;
			Query(1, 1, N, num);
			cout << ans << '\n';
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}