취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25196번 문제인 숲속에서 새 구경하기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25196 

세 새의 종합적인 이동 주기는 Av*Bv*Cv이다. (최소 주기를 보장하지는 않지만, 주기가 아닌 건 아니다.)

현재 [As,Ae], [Bs,Be], [Cs,Ce]가 겹치는 점이 있다면 그중 가장 작은 점을 답으로 출력하자.

그렇지 않다면, 구간의 끝이 가장 작은 구간을 해당 새의 이동주기만큼 shift해주자.

만약 어떤 구간이 세 새의 종합적인 이동주기를 벗어난다면, 모든 가능한 구간을 확인해 본 것이므로 조건을 만족하는 새의 위치는 없다고 결론을 내릴 수 있다.

위 과정을 반복하는 것으로 문제를 해결할 수 있다. 새 A는 Bv*Cv, 새 B는 Av*Cv, 새 C는 Av*Bv번 구간을 이동하면 세 새의 종합적인 이동주기를 벗어나게 되므로, 위의 과정은 최대 O(N^2)회 반복하게 된다. 이는 문제를 해결하기에 충분한 시간복잡도이다.

세 새의 종합적인 이동 주기는 int범위를 넘을 수 있음에 유의하여 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll bound;
ll Alen, Astart, Aend, Blen, Bstart, Bend, Clen, Cstart, Cend;

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

	cin >> Alen >> Astart >> Aend >> Blen >> Bstart >> Bend >> Clen >> Cstart >> Cend;
	bound = Alen * Blen * Clen + 1;
	while (Aend < bound && Bend < bound && Cend < bound) {
		ll L = max(Astart, max(Bstart, Cstart)), R = min(Aend, min(Bend, Cend));
		if (L > R) {
			if (Aend <= Bend && Aend <= Cend) Astart += Alen, Aend += Alen;
			else if (Bend <= Aend && Bend <= Cend) Bstart += Blen, Bend += Blen;
			else Cstart += Clen, Cend += Clen;
		}
		else {
			cout << L;
			return 0;
		}
	}
	cout << -1;
}