[코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제

문제

 

풀이

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;



int main(){
	
	int n, k, pos=0, bp=0, cnt=0, i;
	scanf("%d %d", &n, &k);
	vector<int> prince(n+1);//0으로 초기화 
	
	while(1){
		pos++;
		if(pos>n) pos=1;//pos=9일 경우 1로 pos초기화 
		
		if(prince[pos]==0){
			cnt++;
			if(cnt==k){
				prince[pos]=1;//out
				cnt=0;
				bp++;//n-1명 out명수 체크 
			}
		}
		if(bp==n-1) break;
	}
	
	for(i=1; i<=n; i++){
		if(prince[i]==0){
			printf("%d\n", i);//살아남은 왕자번호출력 
			break;
		}
	}
	return 0;
}

vector배열에 왕자 수만큼 0으로 초기화하고, k만큼 카운트됬을 경우 해당 postion에 있는 왕자 배열을 1로 바꾸어 out된 왕자를 체크해간다. postion이 n보다 클 경우 존재하면 안되기 때문에 1로 초기화한다.

아웃한 왕자의 수가 n-1일 경우 1명만 남게 되니 break하고, 살아남은 왕자의 0인 postion을 출력하면 된다.