[G1] 백준 32644번 랜덤 넘버 추측하기 C++ 세그먼트 트리

리뷰

 

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

오랜만에 풀어본 세그먼트 트리 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 문제를 푼 회원수를 저장할 변수
• m : 당첨 인원수를 저장할 변수
• arr : 각 회원의 가중치를 저장할 배열
• tree : 세그먼트 트리 정보를 저장할 배열

 

함수

1. build

void build( int node, int s, int e )
{
	if ( s == e ) 
		tree[ node ] = arr[ s ];
	else
	{
		int mid = ( s + e ) / 2;

		build( node * 2, s, mid );
		build( node * 2 + 1, mid + 1, e );

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

 

세그먼트 트리 초기화를 위한 함수

 

2. update

void update( int node, int s, int e, int idx )
{
	if ( s == e ) 
		tree[ node ] = 0;
	else
	{
		int mid = ( s + e ) / 2;

		if ( idx <= mid ) 
			update( node * 2, s, mid, idx );
		else 
			update( node * 2 + 1, mid + 1, e, idx );

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

 

세그먼트 트리 업데이트를 위한 함수

 

3. query

int query( int node, int s, int e, int L, int R )
{
	if ( R < s || e < L ) 
		return 0;

	if ( L <= s && e <= R ) 
		return tree[ node ];

	int mid = ( s + e ) / 2;

	return query( node * 2, s, mid, L, R ) + query( node * 2 + 1, mid + 1, e, L, R );
}

 

세그먼트 트리 구간합을 구하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, 각 회원의 가중치를 입력 받아 배열 arr을 초기화한다.
2. build함수를 호출하여 배열 arr을 기반으로 배열 tree를 초기화한다.
3. m개의 쿼리를 수행하고, 각 쿼리의 번호를 변수 c에 입력받는다.
4. query함수를 호출하여 세그먼트 트리의 1~c-1범위의 구간합에 1을 더한 값을 출력 후 공백을 기준으로 구분한다.
5. update함수를 통해 세그먼트 트리의 c번째 리프 노드의 값을 0으로 갱신한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 각 회원의 가중치는 최대 1000이고, 회원수는 최대 50만이므로 int범위 내로 문제 풀이가 가능하다.

 

정답 코드

#include <iostream>
using namespace std;

const int N = 5e5 + 1;
int n, m;
int arr[ N ];
int tree[ N * 4 ];

void build( int node, int s, int e )
{
	if ( s == e ) 
		tree[ node ] = arr[ s ];
	else
	{
		int mid = ( s + e ) / 2;

		build( node * 2, s, mid );
		build( node * 2 + 1, mid + 1, e );

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

void update( int node, int s, int e, int idx )
{
	if ( s == e ) 
		tree[ node ] = 0;
	else
	{
		int mid = ( s + e ) / 2;

		if ( idx <= mid ) 
			update( node * 2, s, mid, idx );
		else 
			update( node * 2 + 1, mid + 1, e, idx );

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

int query( int node, int s, int e, int L, int R )
{
	if ( R < s || e < L ) 
		return 0;

	if ( L <= s && e <= R ) 
		return tree[ node ];

	int mid = ( s + e ) / 2;

	return query( node * 2, s, mid, L, R ) + query( node * 2 + 1, mid + 1, e, L, R );
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );
	cout.tie( 0 );

	cin >> n >> m;
	for ( int i = 1; i <= n; ++i )
		cin >> arr[ i ];

	build( 1, 1, n );

	while ( m-- )
	{
		int c; cin >> c;
		cout << query( 1, 1, n, 1, c - 1 ) + 1 << " ";
		update( 1, 1, n, c );
	}
	//cout << query( 1, 1, n, 1, n );
}