45. 공주구하기

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

8 3

 

출력예제 1 

7

 

풀이 

- 시뮬레이션 문제

- 8명의 왕자를 시계방향, 3번째에 해당하는 왕자를 한명씩 추방

- 입력 변수: n, k(왕자 수, 특정 수)

 

- 풀이법

(1) 벡터배열 0으로 초기화

(2) 무한루프를 돌며 position값을 증가 => 배열의 값이 0이면 cnt++

(3) cnt==k가 될때 cnt를 0으로 초기화, bp++, 해당 위치에 1 넣어줌

(4) 루프를 돌다가 position값이 n보다 커질때, 1로 다시 초기화 => if(pos>n) pos=1;

(5) 루프 돌다가 bp가 n-1, 즉 한 명의 왕자를 제외한 나머지 왕자가 다 추방됬을 때 break;

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

// 45. 공주 구하기(조세퍼스)

int main() {
    int n, k, pos=0, bp=0, cnt=0, i;  //n: 왕자, k: 특정수, bp: 1의 개수 n-1일 시 break, cnt 특정수 만족 check
    scanf("%d %d", &n, &k); //입력
    vector<int> prince(n+1); //1~n
    while(1){
        //bp=n-1이면 break
        pos++;
        if(pos>n) pos=1;
        if(prince[pos]==0){
            cnt++;
            if(cnt==k){
                //왕자 out
                prince[pos]=1;
                cnt=0;
                bp++; //7명 out시켜야 함
            }
        }
        if(bp==n-1) break;
    }
    
    //최종 출력
    for(i=1;i<=n;i++){
        if(prince[i]==0){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}