[백준] 1637 날카로운 눈 (C++)

1637번: 날카로운 눈

라이트모드에서 봐주세요! 다크모드에 이상하게 표시되는 문제가 있어 글자색을 검정으로 설정해두었습니다

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어 볼 수 있는 날카로운 눈을 가진 기이한 원숭이였따. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다.

 

어느 날 멍멍이는 원숭이의 날가로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제는 다음과 같다.

 

정수가 여러 개 모여 있는 정수더미가 있다. 그 안에 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 모두 짝수개 존재한다. 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다.

 

근데 멍멍이가 문제를 전달해 주려다가 생각해보니 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 되는 것이다. 그래서 정수더미 안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.

 

입력

첫째 줄에 입력의 개수 N이 주어진다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB <= C) 의 정수들이 정수더미 안에 있다는 것을 나타낸다. 정수더미는 N개의 입력이 나타내는 정수들을 모두 포함한다.

 

출력

첫째 줄에 정수 두 개를 출력하는데, 첫 번째는 홀수개 존재하는 정수를 출력하고, 두 번째는 그 정수가 몇 개 들어있는지 출력한다. 만약 홀수개 존재하는 정수가 없다면 NOTHING을 출력한다.

 

제한

1 ≤  N ≤  200,000

1 ≤  A, B, C ≤  2,147,483,647

 

 

---

접근 방식

문제 이해

정수가 여러 개 모여 있는 정수더미가 존재한다.

이 중 특정 정수 ‘하나만’ 홀수개 존재하고, 나머지는 짝수개 존재한다.

 

N개의 A, C, B 세트가 주어지는데 이는 A, A+B, A+2B, A+3B, … 의 정수가 더미에 존재함을 의미한다.

(단, A+kB ≦ C)

 

홀수개 존재하는 정수를 구하라.

예시) 입력                   정수 더미에 존재하는 정수 3 1 3 1              ->  1 2 3 3 7 1              ->        3 4 5 6 7 1 7 1              ->  1 2 3 4 5 6 7

 

접근

숫자 범위가 매우 크기 때문에 시간 복잡도에 log가 꼭 들어가야 한다..(고 생각한다..)

 

핵심은 "홀수"개 존재하는 정수가 "오직 하나" 존재한다는 것이다.

 

정수 더미의 최솟값을 lo, 최댓값+1을 hi이라고 하자. mid 는 언제나와 같이 (lo + hi)/2 이다. mid는 개수를 누적해서 합할 때, 경계에 있는 정수(최댓값)를 의미한다. 즉, 주어진 N개의 A, B, C에 대해서, [ai, mid] 구간에 존재하는 개수를 센다. 홀수개 존재하는 정수는 오직 하나이기 때문에, 탐색한 범위가 해당 정수를 포함하면 누적합의 값도 홀수일 것이다.

 

만약 누적합이 홀수라면 다음 탐색 구간은 lo~mid(hi=mid)이 되는 것이고, 누적합이 짝수라면 반대 구간(lo=mid+1)을 탐색한다.

 

간단한 예시를 통해 이해해보자.

ex. n=4 -> 1 10 1 / 4 4 1 / 1 5 1 / 6 10 1

lo = 정수더미의 최솟값
hi = 정수더미의 최댓값 +1

1) lo = 1, hi = 11 → mid = 6

1, 2, 3, 4, 5, 6 / 6개
4 / 1개
1, 2, 3, 4, 5 / 5개
6 / 1개

→ 13개 ; 홀수 → lo ~ mid 구간에 홀수개 존재하는 정수가 있다!!! 따라서, 다음 구간은 lo ~ mid (hi = mid = 3)

2) lo = 1, hi = 6 → mid = 3

1, 2, 3 / 3개
X / 0개
1, 2, 3 / 3개
X / 0개

→ 6개; 짝수 → mid+1 ~ hi 구간에 홀수개 존재하는 정수가 있다!!! 따라서, 다음 구간은 mid+1 ~ hi (lo = mid + 1 = 4)

3) lo = 4, hi = 6 -> mid = 5

1, 2, 3, 4, 5 / 5개
4 / 1개
1, 2, 3, 4, 5 / 5개
X / 0개

-> 11개; 홀수 -> lo ~ mid 구간에 호수개 존재하는 정수가 있다!!! 따라서, 다음 구간은 lo ~ mid (hi = mid = 5)

...

 

다시,

핵심은 "홀수"개 존재하는 정수가 "오직 하나" 존재한다는 것이다.

 

알고리즘

1. 입력 값을 배열에 저장 A, C, B'

     - 이때, 입력 값의 최솟값을 lo에, 최댓값+1을 hi에 저장한다.

2. 이분 탐색

     a. 누적합 구하기

          - N개의 각 경우에 대하여, ai ~ min(C, mid)까지 존재하는 수의 개수를 구하고 모두 더한다.

          - 이때, min(C, mid)가 ai보다 작은 경우에는 0을 더하고 다음 케이스로 넘긴다.

     b. 누적합의 홀짝 여부에 따라 다음 구간을 설정한다.

3. 결과 출력

     a. 홀수개 존재하는 정수 출력

     b. 홀수개 존재하는 정수가 없을 경우 "NOTHING"을 출력한다.

 

시간 복잡도

이분 탐색 - O(logM)

 - 누적합 구하기 - O(N)

 

O(logM)*O(N) → O(NlogM)

 

 

제출

틀렸습니다 → 30% 시간 초과 → 틀렸습니다 → 맞았습니다!!

1. 홀수개 존재하는 숫자가 없는 경우 (출력 결과 NOTHING) 고려를 안 함
2. 모든 int type → long long type 으로 수정
3. hi = __INT_MAX__를 hi = long long(__INT_MAX__)+1 로 수정

* 3. 문제는 주어진 정수 더미의 최솟값, 최댓값을 이용하여 lo, hi 범위를 줄이지 않고, 고정 값을 사용하였을 때 발생하는 문제입니다.

 

Trouble Shooting

lo, hi 고정값 사용 시, hi = long long(__INT_MAX__) + 1 의 이유

반례)
1

2147483647 2147483647 1

hi를 __INT_MAX__(= 2147483647) 로 초기화하면, 위 반례의 경우에 lo=mid+1가 반복되어 2147483647이 될 것이다. 이때, lo==hi 를 만족하므로 while 문이 종료되는데, 결과를 출력하기 전에 2147483647를 mid로 하는 sum 함수(숫자의 개수를 세는 함수)가 실행되지 않는다. 결과적으로, ans 값이 갱신되지 않아 “NOTHING”을 출력하면서 프로그램이 종료된다.

→ 틀린 결과

 

만약에!! 위 입력의 경우 2147483647를 mid로 하는 sum 함수가 실행될 경우에, 이 메서드는 cnt=1 을 반환한다. 이는 cnt%2 != 0 조건을 만족하여, ans = min(ans, mid) 를 거치게 된다. 따라서, ans = min(2147483648, 2147483647)로 ans는 2147483647로 갱신되고, 정상 값을 출력한다.

 

 

Code

코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

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

ll n, a, b, c;
vector<tuple<ll, ll, ll>> vt;
ll hi=0, lo = ll(__INT_MAX__)+1; 

ll sum(ll mid){
    ll cnt = 0;
    for(int i=0; i<n; i++){  
        if(ll(mid) >= get<0>(vt[i])) cnt += (min(mid, get<1>(vt[i])) - get<0>(vt[i]))/get<2>(vt[i]) + 1;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a >> c >> b;
        vt.push_back(make_tuple(a, c, b));
        // lo: 정수 더미의 최솟값, hi: 정수 더미의 최댓값 + 1
        if (lo > a) lo = a;
        if (hi < c) hi = c+1;
    }

    ll ans = ll(__INT_MAX__) + 1;
    while(lo < hi){
        ll mid = (lo + hi) / 2;
        ll cnt = sum(mid);

        if (cnt%2 != 0) {
            hi = mid;
            ans = min(ans, mid);
        }
        else lo = mid+1;
    }

    if(ans == ll(__INT_MAX__) + 1) cout << "NOTHING";
    else cout << ans << " " << sum(ans) - sum(ans-1);
}

 

lo, hi 고정값 사용 Code - C++

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

ll n, a, b, c;
vector<tuple<ll, ll, ll>> vt;
ll hi = ll(__INT_MAX__)+1, lo = 0; // lo, hi 고정값 사용

ll sum(ll mid){
    ll cnt = 0;
    for(int i=0; i<n; i++){  
        if(ll(mid) >= get<0>(vt[i])) cnt += (min(mid, get<1>(vt[i])) - get<0>(vt[i]))/get<2>(vt[i]) + 1;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a >> c >> b;
        vt.push_back(make_tuple(a, c, b));
    }

    ll ans = ll(__INT_MAX__) + 1;
    while(lo < hi){
        ll mid = (lo + hi) / 2;
        ll cnt = sum(mid);

        if (cnt%2 != 0) {
            hi = mid;
            ans = min(ans, mid);
        }
        else lo = mid+1;
    }

    if(ans == ll(__INT_MAX__) + 1) cout << "NOTHING";
    else cout << ans << " " << sum(ans) - sum(ans-1);
}