[결정 문제] CANADATRIP 캐나다 여행

1. 결정 문제

 

이 문제를 결정문제로 해석한뒤 이진법으로 풀어보자

 

D에 k번째 표지판이 있는지?

 

이것을 이진법으로 0 , 8030,000 까지 탐색하면 답이 나올 것이다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
 
int T, N, K;
int L[5000], M[5000], G[5000];
 
bool search(int D)
{
    int sign = 0;
    for(int i = 0; i < N; i++)
        if(D >= L[i] - M[i])
            sign += 1 + (std::min(D,L[i]) - L[i] + M[i])/G[i];
    return sign >= K ;
}
 
int optimize()
{
    int lo = -1, hi = 8030001;
    for(;lo + 1 < hi;)
    {
        int mid = (lo + hi)/2;
        if(search(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}
 
 
int main()
{
    std::cin>>T;
    for(int i = 0; i < T; i++)
    {
        std::cin>>N>>K;
        for(int j = 0; j < N; j++)
            std::cin>>L[j]>>M[j]>>G[j];
        std::cout<<optimize()<<"\n";
    }
}

 

이 문제에서 신경 써야할 건 이진 탐색과 표지판을 세는 것 이다

 

이진 탐색의 경우 search(d - 1) < x <= search(d) 인 d 를 찾아야한다.

 

표지판은

d안쪽에 도시가 있는 경우 (l-m)/g + 1 만큼  있고

d 밖에 도시가 있는경우 l - m 이 작거나 같아야 표지판을 셀 수 있다. (d-(l-m))/g + 1

 

 

 

CANADATRIP