BOJ 3258 : 컴포트

• 문제 링크 : boj.kr/3258
• 난이도 : S3
• 태그 : 시뮬레이션, 브루트포스

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, z, m;
    cin >> n >> z >> m;
    vector<int> arr(n, 0);
    for(int i = 0; i < m; i++) {
        int input;
        cin >> input;
        arr[input-1] = 1;
    }

    for(int k = 1; k < n; k++) {
        int curr = 0;
        while(curr != z-1) {
            curr = (curr + k) % n;
            if(arr[curr]) break;
            if(curr == 0) break;
        }
        if(curr == z-1) {
            cout << k;
            break;
        }
    }

    return 0;
}

---

풀이

k에 대해서 1부터 n-1까지 순차적으로 실행해본다.

특정 값에서 무한루프에 빠지거나 장애물을 만나지 않고 z에 도달하게 된다면 그 k값이 답이다.

작은 수부터 실행해보기 때문에 당연히 가능한 k값 중 최소이다.