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

이소진·2021년 1월 18일
0

#1158 요세푸스 문제
https://www.acmicpc.net/problem/1158

✍어떻게 풀었냐면요

ex)N = 7, k=3

크게 두 가지 방법을 생각했다.
(1번은 시계방향으로 돈다고 생각하면 됨 3-> 6-> 2-> ,,)

  1. 모듈러 연산을 통해 원처럼 연결되어있다고 생각하는 방법이다.(원형큐를 떠올리면 된다) / 숫자 하나가 출력될때마다 크기가 줄어든다는 것을 잘 생각하면서 풀어야한다.
  2. k번째 원소를 만나기 전까지 pop해서 push하는 과정을 반복해준다.
    vector를 이용한다고 했는데 당연 큐를 써도 된다

✍코드(1번 방법)

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

int main() {
    vector<int> a;
    int n, k;
    scanf_s("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)  a.push_back(i);
	
    int index = -1;
    int max = n;

    printf("<");
    for (int i = 0; i < n; i++) {
        index = (index + k) % max;
        //모듈러 연산이 실행되는 부분
        
        printf("%d", a[index]);
        a.erase(a.begin() + index);
        index--; max--; 
        //index--: 출력돼서 삭제되었으므로 그 전값(index-1)으로 부터 k번 떨어진 곳의 원소를 삭제해야한다
        //max--: index는 현재 원소의 총 개수(max)의 나머지로 결정되는데, 삭제되면 총 개수가 하나 줄어들기 때문
        
        if (i == n - 1) printf(">\n");
        else printf(", ");
    }
}

안타깝게도 2번 코드는 쓰다가 사라져버렸다
pop과 push를 적절하게 해주면 된다

profile
webFront / Flutter / iOS 😉

0개의 댓글