B1168

개요

백준 문제 1668번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ???
https://www.acmicpc.net/problem/1668

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

코드

#include <iostream>
using namespace std;
const int MAX = 10001;
int data[MAX];
int N,K;
int * tree;

void initData()
{
	cin >> N >> K;
	int * tmp = (int *)malloc(sizeof(int) * ((N+1)* 4));
	fill_n(tmp,(N+1)*4,-1);
	tree = tmp;

}

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

int getIdx(int start,int end,int node,int K)
{
	if(start == end)
	{
		return start;
	}
	int mid = (start + end) / 2;
	if(K <= tree[node * 2])
	{
		return getIdx(start,mid,node * 2,K);
	}
	else
	{
		return getIdx(mid+1,end,node * 2 + 1,K - tree[node * 2]);
	}
}

void updateTree(int start,int end,int node,int idx)
{
	if(idx < start || idx > end)
	{
		return;
	}
	tree[node]--;
	if(start == end)
	{
		return;
	}
	int mid = (start + end) / 2;
	updateTree(start,mid,node*2,idx);
	updateTree(mid+1,end,node*2+1,idx);
}	

void solve()
{	
	int deleteIdx = 0;
	int findIndex = 1;
	int remainNum = 0;

	initData();
	initTree(1,N,1,tree);
	cout << '<';
	for(int i=0;i<N;i++)
	{
		remainNum = N - i;
		findIndex += K - 1;
		if(findIndex % remainNum == 0)
		{
			findIndex = remainNum;
		}
		else if(findIndex > remainNum)
		{
			findIndex = findIndex % remainNum;
		}
		deleteIdx = getIdx(1,N,1,findIndex);
		updateTree(1,N,1,deleteIdx);
		cout << deleteIdx;
		if(i != N-1)
		{
			cout << ", ";
		}
		else
		{
			cout << ">";
		}
	}


}

int main()
{
	initData();
	solve();

}

코드 수준 메모

segment tree로 탐색을 Nlog(n)의 시간복잡도를 가지게 할 수 있어
segment tree로 배열의 인덱스 합 트리를 구성한다.
이후 삭제할려는 노드의 인덱스를 찾고 가져오면 되는데 그것은 getIdx 함수에서 한다.
그 중 코드를 보면 return getIdx(mid+1,end,node * 2 + 1,K - tree[node * 2]);
위 코드의 K - tree[node * 2]는 루트 노드에서 오른쪽으로 간다.
이 말은 트리 구조상 오른쪽이기 때문에 이동할려는 인덱스 - 왼쪽 노드 인덱스를 해야
정상적인 인덱스 비교를 할 수 있다 그렇지 않으면 오른쪽으로 한번 이동 한 뒤 항상 오른쪽으로 가게 된다.(루트보다 인덱스 값이 더 크기 때문에)
간단하게는 루트 노드와 왼쪽 오른쪽 노드가 같은 인덱스 범위를 갖는다면 어떻게 할 것인지 생각하면 알 수 있다.
update 함수는 삭제할려는 노드를 삭제하는 것인데 이것은 실제로는 해당하는 노드에서부터 루트까지 -1 해주면 삭제하는 효과를 얻을 수 있다.

소감 및 메모

일단은 어려웠다 어려운 문제였고
문제 자체는 저번에 풀었던 문제인데 그 문제에서 시간 제한이 빡빡해져서
O(N^2)으로 풀면 시간초과가 나기 때문에
이전 알고리즘보다 더 빠른 알고리즘을 채택해야하는데
아직 경험이 부족해 그런 알고리즘을 스스로 생각하진 못하고 검색하여 segment tree를 찾아내어 공부를 했다.
위 코드는 segment tree도 공부하고 여러 블로그에서 설명과 코드를 보면서 짠 코드라
내 실력이라 말할 수 없다.

그냥 문제 많이 풀어야함 수구바위