CANADATRIP (중하, p. 454)

문제#

어떻게 풀었나?#

임의의 위치 x에 대해 x이전에 등장한 표지판의 개수 세는 함수를 하나 만들고(Count()) Binary Search로 Count(x)값이 K이상이 되는 x의 최소값을 Binary Search로 찾았다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
ll K;
int L[5001], M[5001], G[5001];
ll Count(int x) {
    ll sum=0;
    for(int i=0; i<N; i++) {
        if(L[i]-M[i]<=x && x<=L[i]) {
            sum += (int)((x-(L[i]-M[i]))/G[i])+1;
        }
        else if(L[i]<x) {
            sum += M[i]/G[i]+1;
        }
    }
    return sum;
}
int main() {
    int tc; cin >> tc;
    while(tc--) {
        cin >> N >> K;
        for(int i=0; i<N; i++) {
            cin >> L[i] >> M[i] >> G[i];
        }

        int lo=0, hi=8030100;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(Count(mid)>=K) hi=mid-1;
            else lo=mid+1;
        }
        printf("%d\n", hi+1);
    }
    return 0;
}

Comment#

ARCTIC 문제 난이도와 같이 ‘중하’정도로 생각하는데, 책은 이 문제의 난이도를 ‘중’으로 표기했다. 그냥 Binary Search 문제. 요즘 코포 문제를 풀어본 적이 없어서 잘 모르지만, Div.2까지만 있던 시절에 문제 C번 수준의 난이도. Rating 1500이 보통 C번 문제라 그러면 이 문제는 1400쯤 되는 것 같다.