C++/공주구하기 + 조세퍼스

인프런 45강 공주구하기 알고리즘 강의를 들었고, 지난번에 봤던 코딩테스트에서 나왔던 문제라 기억이 났다

(아니면 프로그래머스에서 풀었었나..? 암튼 푼 적이 있음)

굉장히 간단한 알고리즘인데 생각해 내는게 쉽지 않았고, 같은 방법을 재활용하면 문제 해결력이 높아질 것 같아서 정리!

 

<문제>

공주 구하기

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은
다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N
번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시
계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그
왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시
1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3
을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7
번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

파이썬 deque를 이용해서 왕자 자리를 아예 빼앗아 버리면(?) 쉽게 풀리는 문제

C++로는 아직 queue를 이용해보지 못했기 때문에 인프런에서 배운 방법을 정리해본다

 

<방법>

동적으로 할당된 prince라는 배열을 이용해, 모든 값을 0으로 초기화 한 후에

K번째 자리를 찾을 때 까지 포지션을 옮긴다.

 

그 K 번째 자리의 값은 1로 변경, 물론 다음 카운팅에서는 제외된다.

pos는 1~N 사이 값이여야하고,1로 설정된 프린스는 n-1개 까지만 허용된다 (마지막 자리를 찾아야하므로)

<코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int n,k,pos=0,i,bp=0,cnt=0;
    scanf("%d %d",&n,&k);
    vector<int> prince(n+1); //range= 1~n
    while(1){
        pos++;
        if(pos>n) pos=1;
        if(prince[pos]==0){
            cnt++;
            if(cnt==k){
                prince[pos]=1;
                cnt=0;
                bp++;
            }
        }
        if(bp==n-1) break;
    }
    for(i=1;i<=n;i++){
        if(prince[i]=0){
            printf("%d\n",i);
        }
    }
    return 0;
}

 

/내가 헷갈린 포인트/

 

1. bp에 대한 조건을 걸 때, while문 맨 첫번째에 넣어야 한다고 생각함.

큰 차이는 없겠지만 결국 while문이 한번 더 도는 셈임. 맨 끝에 넣어도 됨.

 

2. pos++ 와 pos 조건의 순서

순서를 바꾸면 pos가 n이 되었을 때 1로 초기화 하고 아니면 pos++ 하면 된다

 

큰 의미는 없지만 이런 조건식의 실수로 자꾸 포인트 까이게 된다. 조심하자 ㅜ ㅜ

 

 

<백준1158번 조세퍼스>

 

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

이 문제는 제거되는 순서를 배열에 담아 출력하는 문제이다

새로운 배열을 만들어서 제거되는 순서대로 추가해주는 식으로 풀었음.

하지만 deque로 더 멋지게 풀 수 있더군,,,,

공부의 길은 멀다 ^0<