[baekjoon] 11866 : 요세푸스 문제 0

문제

---

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

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

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

 

입력

---

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

 

출력

---

예제와 같이 요세푸스 순열을 출력한다.

 

예제 입출력

---

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

11866번: 요세푸스 문제 0

 

문제 풀이

---

간단하다고 생각했지만 생각보다 간단하지 않았다. 벡터에 N의 크기만큼 만들어 0으로 초기화시켜두고 K번째 숫자를 출력후 그에 해당하는 벡터를 1로 바꿔준다. 이미 1일경우 continue를 사용해 넘어가주려 했으나 시간초과로 돌아가지지 않았다. 그래서 1일경우를 빼고 0일때만을 뜻하는 if문을 사용하여 그안에 모든 조건을 넣어주었다. 그랬더니 다행히 제대로 돌아가게 된다.

 

최종 코드

---

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> v(N, 0);
    int j = 0;
    int i = 0;
    int count = 0;

    cout << "<";
    while (count < N) {
        if (v[j] == 0) {
            i++;
            if (i == K) {
                cout << j + 1;
                v[j] = 1;
                count++;
                if (count < N)
                    cout << ", ";
                i = 0;
            }
        }
        j++;
        if (j == N)
            j = 0;
    }
    cout << ">";
}