백준 11866번 요세푸스 문제 0 [C++]

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

11866번: 요세푸스 문제 0

문제 간단 정리

원으로 앉아있고 K번째마다 제거되기 때문에 K 번째가 아닐때는 제외하고 큐를 사용하여 뒤를 넘겨주면 

구현이 가능할테지만... 큐를 사용하지 않고 풀었다, 큐를 사용해서 푼 블로그 참조 https://cocoon1787.tistory.com/234

 

하지만 나는 그냥 큐 사용을 안하고 구현될 것 같아서 다르게 풀었다.

문제 해결 방법

대략 내가 직접 하나하나 세가면서 한다 생각하고 구현하였다.

수를 제거함을 알기위해서 count 변수, 지금 가리키고 있는 수인 포인터 index 변수

수가 제거되었는지 체크하기 위해서 bool 변수 flag를 설정해 두었다.

flag가 false라면 count++(그 수를 지나감을 의미) ,

count가 K(번째 수)가 되었다면 그 수를 제외하고(flag를 true로) 정답에 넣기

정답의 수가 총 N의 개수와 같아진다면 break;

만일 index가 범위를 벗어났다면 1로 초기화

전체 코드

#include<vector>
#include <iostream>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    int index = 1, count = 0;
    bool flag[1001] = { 0, };
    vector<int> ans;

    while (1) {


        if (flag[index] == false) {
            
            count++;

            if (count == K) {
                ans.push_back(index);
                flag[index] = true;
                count = 0;
            }
        }

        if (ans.size() == N) {
            break;
        }

        index++;
        if (index > N) {
            index = 1;
        }

        //cout << "index:" << index << "\n";
    }

    cout << "<";
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size() - 1) {
            cout << ans[i] << ">";

        }else cout << ans[i] << ", ";


    }

}