안경잡이개발자

728x90
반응형

문제 유형: 정수론

문제 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;

}


728x90
반응형

Comment +0