백준 1637번: 날카로운 눈 (C++)

접근

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

1637번: 날카로운 눈

문제 풀이에 전혀 감을 잡지 못해서 결국 다른 분의 풀이 및 해설을 보고나서야 이해하게 되었다.

https://kibbomi.tistory.com/205

boj, 백준) 1637. 날카로운 눈 (C/C++)

링크의 풀이를 참고하였다.

주어지는 수 중 홀수개인 수가 한 개 뿐이므로, 그 홀수개인 수를 포함하여 개수를 세면 홀수개이고, 포함하지 않고 세면 짝수개인 것을 이용하는 문제이다. 위의 원리를 알고 전체 범위 1 ~ N 중 이분 탐색으로 갯수를 계속 세어나가면서 범위를 줄여 홀수개인 수를 찾아나갈 수 있다.

1 ~ N 범위에서 중간값인 N/2 를 mid 로 잡고 1~mid 범위에 있는 수의 갯수를 세어준다. 만약 이 수가 홀수라면 정답의 수는 1 ~ mid 범위 안에 있으므로 end 값을 mid - 1 로 바꾸어주고, 이 수가 짝수라면 정답의 수는 mid ~ N 범위 안에 있으므로 start 값을 mid + 1 로 바꾸어준다. 이러한 탐색을 계속 해나가면 만나는 값이 바로 정답의 수가 된다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

#define endl '\n'

struct ITEM {
    int a;
    int c;
    int b;
};

int N;
ITEM Item[20001];

long long Count(long long mid) {
    if (mid == 0) return 0;
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        long long num = 0;
        long long val = min((long long)Item[i].c, mid) - Item[i].a;
        num = val < 0 ? 0 : val / Item[i].b + 1;
        sum += num;
    }
    return sum;
}

void Solve() {
    int ans = -1;
    long long left = 0;
    long long right = 2147483647;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (Count(mid) % 2 == 0) {
            left = mid + 1;
        } else {
            ans = (int)mid;
            right = mid - 1;
        }
    }
    if (ans == -1) {
        cout << "NOTHING" << endl;
    } else {
        cout << ans << ' ' << Count(ans) - Count(ans - 1) << endl;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    int a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> c >> b;
        Item[i] = {a, c, b};
    }
    Solve();

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!