문제
원형으로 배치된 n개의 정류장에서 버스가 k 간격으로 순환할 때, 목적지 z에 도달할 수 있는 최소 간격 k를 구하는 문제다. 단, 특정 정류장(고장난 곳)을 거치지 않아야 한다.
입력
- 한 줄에 n, z, m이 주어진다.
- 이후 m개의 줄에 걸쳐 고장난 정류장 번호가 주어진다.
출력
- 조건을 만족하는 최소 간격 k를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 3 1 5 | 2 |
풀이
가능한 모든 간격 k를 1부터 순서대로 시도하면서 조건을 만족하는 최소값을 찾는 브루트포스 시뮬레이션이다.
- m개의 고장난 정류장을 배열 d에 표시한다.
- m이 0이면 k=1로 어떤 간격도 가능하므로 1을 출력한다.
- k를 1부터 증가시키며 시뮬레이션: 정류장 1에서 출발하여 k씩 이동 (mod n).
- 방문한 정류장이 고장난 곳이면 중단, 목적지 z(mod n)에 방문 표시가 있으면 해당 k를 출력한다.
핵심 아이디어: 방문 배열 v를 사용해 순환을 감지하고, 각 k에 대해 시작점(1)으로 돌아오거나 고장난 정류장을 만나면 탐색을 중단한다.
코드
#include <iostream>
using namespace std;
int main()
{
int n, z, m;
cin >> n >> z >> m;
int d[1000] = {};
int g;
for (int i = 0; i < m; i++)
{
cin >> g;
d[g] = 1;
}
if (m == 0)
{
cout << "1";
return 0;
}
int v[1000] = {};
int t;
for (int i = 1; i < 999; i++)
{ // k
t = 1;
for (int j = 0; j < 999; j++)
{
v[j] = 0;
}
while (v[t] == 0)
{
if (d[t] == 1)
{
break;
}
v[t] = 1;
t += i;
t = t % n;
}
if (v[z % n] == 1)
{
cout << i;
return 0;
}
}
}복잡도
- 시간: O(N²) — 최대 N가지 간격 k를 시도하며 각 시뮬레이션은 최대 N번 이동
- 공간: O(N) — 고장난 정류장 배열 d와 방문 배열 v