[BOJ] #1158 요세푸스 문제

시간 제한	메모리 제한	정답 비율
2초	256MB	49.068%

 

1158번: 요세푸스 문제

 

문제

해결

key point, %(나머지연산자)를 활용한다.

예제에서는 입력으로 '7, 3' 이 주어졌으므로 이대로 해보면

1. 처음 시작을 0으로 잡으면 3번째 사람은 2이고 2번인 사람은 제거될 수 있으므로
   1. chk[2] = 1, 표시하고
   2. 0부터 시작했으므로 현재위치를 나타내는 idx에서 +1을 더한 값을 출력한다. → 3
   3. 그리고 num을 1 증가시킨다. (num은 제거된 사람의 수를 세는 변수.) : num = 1
2. 또 다음 위치에 가기 위해서 카운트 세 번을 하고 다음 위치를 찾아간다.
   1. 만약 해당 위치의 사람을 제거했었다면 chk[idx] = 1 이었을 테니 cnt를 증가시키지 않는다.
3. 그렇게 다음 위치인 5를 찾아가서 6을 출력하고 chk[6] = 1, num++.를 해준다.

... 반복 하다보면

num = 6 일 때가 오게 되고, 다음 위치를 가리키는 idx 는 제거되지 않은 마지막 사람을 가리키고 있으므로 >와 같이 출력하고 반복문을 종료한다. 

 

코드

메모리	시간
2004KB	1740ms

#include <iostream>
using namespace std;
int n, k, chk[5005], idx, num;
int main() {
    scanf("%d %d", &n, &k);
    idx = k - 1;
    printf("<");
    while (1) {
        if (num == n - 1) {
            printf("%d>", idx + 1);
            break;
        }
        else if (!chk[idx]) {
            num++;
            chk[idx] = 1;
            printf("%d, ", idx + 1);
        }
        int cnt = 0;
        while (cnt < k) {
            idx = (idx + 1) % n;
            if (!chk[idx]) cnt++;
        }
    }
    return 0;
}

 

후기

처음풀었을 때 보다 메모리를 20kb줄였고, 시간도 52ms가 줄었다.

• 1 부터 N까지 저장하는 배열을 만들지 않았기 때문에 메모리도 줄고, 배열 접근 시간도 없었기 때문에 이런 차이가 생긴것 같다.

그리고 아쉽게 한 번 틀렸었는데 자꾸 k가 들어갈 곳에 상수를 적어놔서 한번씩 틀리는 것 같다.. 어휴
마음만 급해서 이난리!!