백준 1158번 : 요세푸스 문제 [C++]

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

 

이 문제는 전에 파이썬으로 풀어봤었는 데 C++ 공부 겸 cpp로 다시 풀어보았다. 

풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> person(N);       // N명의 벡터 생성
    vector<int> deletePerson; // 삭제되는 사람 순서 벡터 (요세푸스 순열 담을 벡터)

    // 벡터에 값 넣기
    for (int i = 0; i < N; i++)
    {
        person[i] = i + 1;
    }

    int index = 0;
    while (!person.empty())
    {
        index = (index + K-1) % person.size();
        deletePerson.push_back(person[index]); // 삭제할 사람 번호 담고
        person.erase(person.begin() + index);      // 삭제
    }

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

    return 0;
}

 

- push_back으로 값을 넣어줄 거기 때문에 deletePerson의 초기선언을 하지 않았다. 

deletePerson(N)으로 설정해두면 마지막 출력 때 <0, 0, 0, 0, 0, 0, 0, 3, 6, ... > 이렇게 출력된다. 

 

핵심

이 문제의 핵심은 삭제할 인덱스를 찾는 것인데 

K번째 사람을 없앤다고 무작정 인덱스를 K로 한다면 이 문제는 풀지 못한다. 

 

누적으로 K번째를 찾아 없애야하기 때문에 index = index + (K-1)까지는 쉽게 생각할 수 있다. (K번째는 인덱스에서 K-1이다)

K=3일때 

3번째인 인덱스 2(숫자 3)를 삭제하고 그 다음 3번째는 6이다. 1 2 3 4 5 6 7 

6의 인덱스는 남은 1 2 4 5 6 7 에서 살펴봐야하므로 인덱스는 4이다. index(2) + 3 -1 = 4 (성립)

 

이제 여기서 문제인데..

6 다음의 3번째는 2이다. 2의 인덱스는 1 2 4 5 7에서 1이 된다. 

index(4) + 3 - 1 = 6 인데... 어떻게 1을 만들까?

배열의 size를 나눈 후의 나머지(%)가 바로 인덱스 값이 된다. 

index(4) + 3 - 1 % size(5) = 6 % 5 = 1

 

앞의 식도 다시 보자. 

3번째 숫자인 3, 인덱스 2 

index(0) + 3 - 1 % size(7) = 2 % 7 = 2

 

그 다음 3번째 숫자인 6, 인덱스 4

index(2) + 3 - 1 % size(6) = 4 % 6 = 4

 

 

아... 다시 풀어도 쉽지 않은 것 같다...

그리고 c++ 공부도 해야겠다.....

 

알고리즘은 너무 어렵다 후ㅠ구ㅠ

 

 

파이썬 버전 보러가기