[P5] 백준 3895번 그리고 하나가 남았다 C++ 세그먼트 트리

리뷰

 

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

요세푸스 문제와 유사한 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 돌의 개수를 저장할 변수
• k : 건너 뛸 돌의 개수를 저장할 변수
• m : 초기 돌의 번호를 저장할 변수
• tree : 세그먼트 트리 정보를 저장할 배열

 

함수

1. build

void build(int node, int s, int e) {
	if (s == e) tree[node] = 1;
	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. query

int query(int node, int s, int e, int k) {
	if (s == e) {
		tree[node] = 0;
		return s;
	}
	int mid = (s + e) / 2;

	int result = k <= tree[node * 2] ? query(node * 2, s, mid, k) : query(node * 2 + 1, mid + 1, e, k - tree[node * 2]);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	return result;
}

 

도달한 돌을 제거하고, 세그먼트 트리의 업데이트 및 해당 돌의 번호를 리턴하기 위한 함수

 

 

문제풀이

1. n, k, m값을 입력 받고, 모든 값이 0일 경우 break처리한다.
2. build함수를 통해 리프 노드가 1인 상태로 누적합 세그먼트 트리 초기화를 진행한다.
3. 변수 idx을 m, res를 임의의 값으로 출력한다.
4. n번의 for문을 개행하고, 매 루프마다 query함수를 호출하여 idx번째 돌을 제거 후 돌의 번호를 res에 저장한다.
5. 기저 조건으로 i가 n에 도달한 경우 마지막 돌이 남은 상태이므로 break처리한다.
6. idx를 idx-1+k를 루트 노드의 값으로 나눈 나머지로 저장한다.
7. 만약 idx가 0인경우 idx를 루트 노드의 값으로 저장한다.
8. res에 저장된 값을 출력 후 개행문자를 삽입한다.
9. 위 로직을 테스트케이스가 종료될 때 까지 반복한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. idx-1+k를 세그먼트 트리의 총 합으로 모듈러연산을 하면서 자동으로 다음 돌의 위치를 알 수 있다.
2. 하지만 1-based-indexing인 상태에선 idx가 0인 경우를 분기처리해야한다.
3. 마지막 돌이 남은 경우엔 break처리를 해주어야 무한루프를 방지할 수 있다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e4 + 1;
int n, k, m;
int tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = 1;
	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];
	}
}

int query(int node, int s, int e, int k) {
	if (s == e) {
		tree[node] = 0;
		return s;
	}
	int mid = (s + e) / 2;

	int result = k <= tree[node * 2] ? query(node * 2, s, mid, k) : query(node * 2 + 1, mid + 1, e, k - tree[node * 2]);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	return result;
}

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

	while (1) {
		cin >> n >> k >> m;
		if (!n && !k && !m) break;
		build(1, 1, n);

		int idx = m, res = -1;
		for (int i = 1; i <= n; ++i) {
			res = query(1, 1, n, idx);
			if (i == n) break;

			idx = (idx - 1 + k) % tree[1];
			if (idx == 0) idx = tree[1];
		}
		cout << res << "\n";
	}
}