네 개의 숫자 p, a, b, c가 주어져 있다고 가정해 보겠습니다. 수영장에는 세 명의 선수가 있으며, 각 선수는 수영장을 한 번 건너고 되돌아오는 데 각각 a분, b분, c분이 걸립니다. 따라서 출발 시점을 기준으로 첫 번째 선수는 0, a, 2a, 3a… 분째에, 두 번째 선수는 0, b, 2b, 3b… 분째에, 세 번째 선수는 0, c, 2c, 3c… 분째에 수영장 왼쪽 끝(출발 지점)에 위치하게 됩니다.
선수들이 수영을 시작한 지 p분 후에 우리가 수영장을 방문한다면, 적어도 한 명의 선수가 왼쪽 끝에 도착할 때까지 최소 얼마나 기다려야 하는지 구하는 것이 이 문제의 목표입니다.
예제 입력과 출력
예를 들어 입력이 p = 2, a = 6, b = 10, c = 9라고 해보겠습니다. 이때 출력은 4입니다. 2분째에 수영장에 도착하면 첫 번째 선수는 6분째에야 되돌아오므로, 4분을 기다려야 하기 때문입니다.
해결 접근 방법
이 문제는 모듈로(나머지) 연산만으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 선수가 왼쪽 끝에 있는 시점은 항상 해당 선수의 주기(a, b 또는 c)의 배수입니다.
- 현재 시점에서 각 주기의 다음 배수까지 남은 시간을 계산하면, 그 값이 곧 기다려야 하는 시간이 됩니다.
- 세 선수 중 가장 짧은 대기 시간을 선택하면 정답입니다.
이를 단계별로 정리하면 다음과 같습니다.
(p 값을 1 감소시킨다)
(a - (p mod a + 1)), (b - (p mod b + 1)), (c - (p mod c + 1)) 중 최솟값을 반환한다
즉, 나머지 연산을 활용해 각 선수가 다음으로 왼쪽 끝에 도착하기까지 남은 시간을 구하고, 그중 최솟값을 반환하는 방식입니다. 이 알고리즘의 시간 복잡도는 상수 시간인 O(1)로 매우 효율적입니다.
C++ 구현 예제
더 나은 이해를 위해 아래 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int p, int a, int b, int c) {
p--;
return min(a - (p % a + 1), min(b - (p % b + 1), c - (p % c + 1)));
}
int main() {
int p = 2;
int a = 6;
int b = 10;
int c = 9;
cout << solve(p, a, b, c) << endl;
}
입력
2, 6, 10, 9
출력
4
코드에서는 먼저 p를 1 감소시킨 뒤, 각 선수의 주기에 대해 나머지 연산을 적용하여 다음 도착 시점까지의 대기 시간을 계산합니다. 그런 다음 세 값 중 최솟값을 반환함으로써, 적어도 한 명의 선수를 만나기 위해 기다려야 하는 최소 시간을 손쉽게 구할 수 있습니다.