백준 17078번 원 위의 개미

문제

택희는 원 하나를 갖고 있고, 그 원의 둘레를 일정한 속도로 기어다니는 개미 M마리를 키우고 있다. 각 개미들의 크기는 무시할 수 있을 정도로 매우 작다.

어느 날 택희는 원주를 N(≥M)등분하는 점을 찍고, 각 지점에 시계방향으로 1, 2, 3, …, N의 번호를 붙였다. 각 지점의 번호를 시계방향으로 읽으면 1, 2, 3, …, N이 되며, N번 지점 다음에는 1번 지점이 있게 될 것이다. 그 후, 모든 개미가 서로 다른 어떤 지점 위에 있도록 개미들을 놓았다. 개미들은 시계방향 또는 반시계방향의 초기 방향을 바라보고 있으며, 택희가 “시작”을 외치면 모든 개미들은 바라보고 있는 방향으로 이동하게 된다. 시작 시각은 0이며, 그 이후 정확히 1초마다 개미들은 다음 지점에 도착한다.

모든 개미는 동일한 속력으로 이동하다가, 서로를 마주칠 경우 그 즉시 방향을 바꾸어 돌아가게 된다. 개미들은 무한히 움직이며 택희가 찍은 N개의 점을 밟고 지나다니게 될 것이다.

택희는 개미들의 초기 위치와 방향에 따라, 같은 시간동안 상대적으로 조금 더 많이 밟히는 지점들이 있을 것이라 생각했다. 하지만 개미들은 멈추지 않기 때문에, 실제로 그런 지점이 있는지는 확인할 수가 없었다.

개미들은 시각 0에 자신이 서 있는 지점을 밟고 있으므로, 개미가 초기에 서 있는 모든 지점은 시각 0에 밟힌 횟수가 1이며, 아닌 모든 지점은 시각 0에 밟힌 횟수가 0이다. 또한, 개미 두 마리가 동시에 어떤 지점을 밟을 경우, 그 지점은 그 시각에 두 번 밟힌 것으로 센다.

택희는 자신이 세운 가설을 실험할 프로그램이 필요하다고 판단하였다. 정확히는, 어떤 지점 P가 X번 이상 밟히게 되는 최초의 시각이 여러 개 궁금해졌다. 택희를 위해, 이러한 질의를 빠르게 해결해 줄 프로그램을 작성해보도록 하자.

문제풀이

사용한 알고리즘 : 이분탐색

(0) 생각

 개미들이 부딪치면 완전 탄성충돌을 합니다.

 이것을 잘 생각해보면, 그냥 개미는 충돌이 없이 진행한다고 생각해도 됩니다.

 따라서 N초 후 ( 개미 한마리가 한바퀴 도는데 N초 걸림 ) 모든 지점은 M번 밟히게 됩니다.

(1) 코드 29~36

 위 생각에 따라, cnt = q*M + r 만큼 밟힌다고 생각합니다. ( 단 0 < r <= M )

 즉, 어떤 지점이든 q*M 번만큼 밟히는 건 q*N 시간 만큼이 필요합니다. 

 추가로 r 만큼 밟히는 시간만 구해주면 되는 것이죠.

 단, cnt가 M의 배수인 경우, r = M 으로 생각해 줄 것입니다.

 모든 지점이 N 시간 주기로 M번씩 밟히는 것은 맞습니다만, 각 지점마다 N주기 중 밟히는 시간이 다르기 때문입니다.

 예를 들어 N=4, M=2 이고, 1번 위치에 개미가 시계방향, 3번 위치에 개미가 반시계방향일 때 

 모든 위치는 4초마다 2번씩 밟히지만, 4초의 주기 속, 각 지역이 밟히는 시간은

지역	1	2	3	4
2번 밟히는 시간	2초	1초	2초	3초

 일 것입니다.

(2) 코드 38~71

 위에서 언급한 추가로 밟히는 r 번에 걸리는 시간을 계산합니다. ( 0 < r <= M )

 어떤 x 지역이 r만큼 밟히는 시간을 이분탐색으로 찾습니다.

 x에서 k만큼 떨어진 지역에 있는 개미가 x지역을 밟으려면 k 초의 시간이 걸릴 것입니다.

 최소 0, 최대 N-1 ( x에서 최대로 떨어진 지역과 x와의 거리는 N-1 입니다.) 으로 놓고,

 r번만큼 밟히려면 몇 초가 ( 얼마만큼의 거리가 ) 필요한지 계산합니다.

 

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 111111;
	int N, M, Q;
	int pSum_cw[MAX]; // pSum_cw[x] : 1~x 까지 clockwise 가는 개미 수
	int pSum_ccw[MAX];
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M >> Q;
	for (int i = 0; i < M; ++i) {
	int x, d;
	cin >> x >> d;
	if (d == 0) pSum_cw[x] = 1;
	else pSum_ccw[x] = 1;
	}
	for (int i = 1; i <= N; ++i) {
	pSum_cw[i] += pSum_cw[i - 1];
	pSum_ccw[i] += pSum_ccw[i - 1];
	}
	for (int i = 0; i < Q; ++i) {
	int x, cnt;
	cin >> x >> cnt;
	// 모든 개미는 k*N 초 후 자기 자신으로 돌아옴
	// 한바퀴에 N초 : 한바퀴에 모든 칸은 M번 밟힘
	long long ans1 = 1LL * (cnt / M) * N; // long long 제발....
	cnt %= M;
	if (cnt == 0) { // 단 딱 맞게 떨어지면 마지막 바퀴는 계산해줄꺼임
	cnt += M;
	ans1 -= N;
	}
	//일단 ans1 초 만큼 (바퀴수 * N 만큼) 걸렸고, cnt 번 만큼 더 밟혀야함
	long long ans2 = 1LL * (N - 1);
	int l = 0; // 최소 시간
	int r = N - 1; // 최대 시간
	while (l <= r) {
	int mid = (l + r) / 2;
	// 왼쪽에서 오는 clock wise 들
	int left = x - mid;
	int sum1 = 0;
	if (left >= 1) // left 이상 ~ x 이하
	sum1 = pSum_cw[x] - pSum_cw[left - 1];
	else {// 1~x 까지 + left~N 까지
	left += N;
	sum1 = pSum_cw[x] + pSum_cw[N] - pSum_cw[left - 1];
	}
	// 오른쪽에서 오는 counter clock wise 들
	int right = x + mid;
	int sum2 = 0;
	if (right <= N) // x 이상 right 이하
	sum2 = pSum_ccw[right] - pSum_ccw[x - 1];
	else { // 1이상 right 이하 + x이상 N이하
	right -= N;
	sum2 = pSum_ccw[right] + pSum_ccw[N] - pSum_ccw[x - 1];
	}
	// 합이 cnt 이상
	if (sum1 + sum2 >= cnt) {
	ans2 = 1LL * mid;
	r = mid - 1;
	}
	else
	l = mid + 1;
	}
	cout << ans1 + ans2 << '\n';
	}
	return 0;
	}

view raw BOJ 17078.cpp hosted with ❤ by GitHub