코드 포스(Code Force) 1055 - C. Lucky Days

문제 유형: 정수론

문제 URL: https://codeforces.com/contest/1055/problem/C

  앨리스(Alice)와 밥(Bob)은 모두 각각 일정한 컨디션 주기가 있습니다. 운이 좋은(Lucky) 날이 몇 일 계속된 이후에, 그 이후에는 운이 나쁜(Unlucky) 날이 몇 일간 계속되는 방식입니다. 이 때 앨리스와 밥이 둘 다 운이 좋은(Lucky) 날이 최대 몇 일 겹칠 수 있는지를 구하면 되는 문제입니다.

  예를 들어 앨리스는 0일부터 2일까지 운이 좋고, 주기가 5라고 가정합시다. 또한 밥은 1일부터 3일까지 운이 좋고, 주기가 5라고 가정합시다. 이 때 운이 좋은 날을 1로, 운이 나쁜 날을 0으로 표현하면 다음과 같습니다. 둘 다 운이 좋은 날은 최대 2일이군요.

  0 1 2 3 4 5 6 7 8 9

  1 1 1 0 0 1 1 1 0 0

  0 1 1 1 0 0 1 1 1 0

  이 문제는 날짜가 0일부터 10억 일까지 입력될 수 있다는 점에서 사실상 상수 시간 안에 답을 도출할 수 있는 알고리즘이 필요합니다. 이는 '특정 주기'로 반복된다는 점에서 조금만 생각해보면 쉽게 구할 수 있습니다.

  바로 앨리스의 주기와 밥의 주기의 최대 공약수(GCD)를 구하는 것입니다. 최대 공약수를 기준으로 앨리스 혹은 밥의 주기를 '슬라이딩'하여 운이 좋은 날이 최대 얼마나 겹치는지 확인할 수 있기 때문이죠. 예를 들어 최대 공약수가 3이 나왔다면, 앨리스 혹은 밥의 컨디션 주기를 3만큼 시프트(Shift) 할 수 있는 것입니다. 왼쪽 혹은 오른쪽으로요. 

  따라서 전체 4가지 경우만 고려하면 돼요.

  1) 좋은 운이 시작되는 날이 A가 B에 비해 먼저 있을 때

  1-1) A가 B의 최대한 왼쪽에 붙는 경우를 계산하기.

  1-2) A가 B의 최대한 오른쪽에 붙는 경우를 계산하기.

  2) 좋은 운이 시작되는 날이 B가 A에 비해 먼저 있을 때

  2-1) B가 A의 최대한 왼쪽에 붙는 경우를 계산하기.

  2-2) B가 A의 최대한 오른쪽에 붙는 경우를 계산하기.

  위 4가지 경우를 모두 고려하여 최대한 많이 겹칠 수 있는 일자를 구하면 됩니다. 따라서 유클리드 알고리즘을 이용하여 사실상 상수에 가까울 정도로 빠른 속도로 답을 도출할 수 있는 것입니다.

※ 입출력 예시 ※

input

Copy

0 2 5
1 3 5

output

Copy

2

input

Copy

0 1 3
2 3 6

output

Copy

1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <limits.h>

using namespace std;

int gcd(int a, int b) {
	if(a == 0)
	return b;
	return gcd(b % a, a);
}

int main(void) {
	int la, ra, ta, lb, rb, tb;
	cin >> la >> ra >> ta >> lb >> rb >> tb;
	int pat = gcd(ta, tb);
	int res = 0;
	int gap = abs(la - lb) / pat;
	// a가 b보다 더 앞에 있을 때 
	if(la < lb) {
		int temp = la + pat * gap; // a가 b의 최대한 왼쪽에 붙는 경우 
		res = max(res, (temp + 1 + (ra - la)) - lb); 
		temp = la + pat * (gap + 1); // a가 b의 최대한 오른쪽에 붙는 경우 
		res = max(res, (1 + rb) - temp); 
	}
	// b가 a보다 더 앞에 있을 때
	else {
		int temp = lb + pat * gap; // b가 a의 최대한 왼쪽에 붙는 경우
		res = max(res, (temp + 1 + (rb - lb)) - la); 
		temp = lb + pat * (gap + 1); // b가 a의 최대한 오른쪽에 붙는 경우 
		res = max(res, (1 + ra) - temp);
	}
	// 두 사람의 운이 좋은 날이 계속되는 길이보다 커질 수는 없음 
	res = min(res, rb - lb + 1);
	res = min(res, ra - la + 1);
	cout << res;
	return 0;
}