[BOJ] 1637번 : 날카로운 눈

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

1637번: 날카로운 눈

 

한참을 들여다봐도 풀 방법이 떠오르지 않아 푼 사람들로부터 힌트를 얻어 풀었다. binary search의 참신한 적용 문제이다.

 

그냥 brute-force를 쓰면 time complexity가 대략 20000* 2^32가 나오게 된다. 고로 다른 방법을 찾아야 한다.

 

이 문제에서는 범위를 잘라서 그 안에 있는 수들의 개수를 모두 세었을 때, 짝수 개면 그 안에 홀수인 숫자가 없고, 전체 개수가 홀수 개면 그 안에 홀수 개인 숫자도 존재한다는 점에서 착안하여 binary search를 한다.

 

그러려면 또 한 가지, O(1)로, 특정 한계(lim이라고 하자) 안에 있는 숫자들의 개수를 구하는 공식이 필요하다. 이는 다음과 같이 구할 수 있다.

이때 b[i]로 나누고 다시 곱해주는 과정은 lim이 b[i]*x + a[i] 로 표현되는 값이 아닐 경우 그 부분을 정수형 연산을 통해 버려주기 위함이다. 즉,  lim에서 a[i]를 빼고 b[i]로 나누어 줌으로써 b[i]가 몇 번이 곱해져서 lim보다 작은 최대의 b[i]*x +a[i]꼴 정수를 만들 수 있는가를 알아내고, 그 값에 다시 b[i]를 곱하고 a[i]를 더해줌으로써 최대 정수를 얻는다.

 

두 최대 정수 사이에 몇 개의 숫자가 있는가는 다음의 공식으로 구할 수 있다.

right를 더 큰 수, left를 더 작은 수라고 할 때 다음으로 구할 수 있다.

 

이 방법을 바탕으로 계산을 하되, 몇 가지 제약 조건을 더해서 코딩해 주면 된다.

내가 곤욕을 치렀던 부분은 계산해야 할 범위(left, right)와 공식을 통해 수의 개수를 계산하는 범위 간의 관계를 어떻게 해야 잘못된 셈을 방지할 수 있는가에서 착오를 하여 시간을 크게 낭비하였다..

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxN = 20050;
int n;
long long int a[maxN], c[maxN], b[maxN];
 
bool isOdd(long long int x) {
    if(x%2==1) return true;
    return false;
}
 
long long int floor(int i, long long int lim) {
    return ((lim-a[i])/b[i])*b[i]+a[i];
}
 
long long int countRange(long long int left, long long int right) {
    long long cnt = 0;
    long long int lVal, rVal;
    long long int lLim, rLim;
    for(int i = 1; i <= n; i++) {
                             
        lLim = max(left, a[i]); rLim = min(right,floor(i,c[i]));
        lVal = floor(i, lLim);
        if(lVal<left) lVal+=b[i];
        rVal = floor(i,rLim);
        
        if(rVal >= lVal && rLim >= lLim) cnt+=(rVal-lVal)/b[i]+1;
        
    }
    return cnt;
}
 
int main ( void ) {
    
    long long int left=2147483648, right=0, mid;
    
    scanf("%d", &n);
    for(int i=1; i <=n; i++) {
        scanf("%lld %lld %lld", &a[i], &c[i], &b[i]);
        left=min(left,a[i]);
        right=max(right,c[i]);
    }
    
    if(!isOdd(countRange(left,right))) {
        printf("NOTHING\n");
        return 0;
    }
    mid=(left+right)/2;
    
    while(left!=right) {
        
        if(isOdd(countRange(left,mid))) {
            right=mid;
            mid=(left+right)/2;
        }
        else {
            left=mid+1;
            mid=(left+right)/2;
        }
    }
    
    cout<<left<<" "<<countRange(left,right)<<endl;
    
}

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1637/1637.cpp

Jordano-Jackson/PS