캐나다 여행 :: 알고스팟

문제 : https://algospot.com/judge/problem/read/CANADATRIP

문제

동건이는 여름 방학을 맞아 자동차를 끌고 캐나다 횡단 여행을 떠나기로 했습니다. 캐나다의 1번 고속도로는 세계에서 가장 긴 고속도로 중 하나로, 캐나다의 동쪽 끝에서 서쪽 끝까지 있는 모든 주요 도시를 연결합니다. 동건이는 이 고속도로를 타고 캐나다의 서쪽 끝 빅토리아에서 동쪽 끝 세인트 존까지 8,030km 를 달리기로 마음먹었습니다.

이 고속도로는 굉장히 많은 표지판이 있기로도 유명합니다(이 문장부터는 사실이 아닙니다..). 이 고속도로는 N개의 주요 도시를 지나치는데, 각 도시까지의 남은 거리를 나타내는 표지판이 많기 때문입니다. i번째 도시까지의 거리를 나타내는 표지판은 도시에 도착하기 Mi미터 전부터 시작해서 도시에 도착할 때까지 Gi미터 간격으로 설치되어 있습니다. 예를 들어 M0=500이고 G0=50이라고 하면 여행자는 다음과 같은 11개의 표지판을 순서대로 보게 됩니다.

• "0번 도시 500미터 전"
• "0번 도시 450미터 전"
• ...
• "0번 도시 50미터 전"
• "0번 도시: 환영합니다"

시작점으로부터 각 도시까지의 거리 Li와 Mi, Gi가 주어질 때, 시작점으로부터 여행하면서 동건이가 보게 되는 K번째 표지판의 위치를 계산하는 프로그램을 작성하세요. 한 위치에 표지판이 여러 개 있을 경우에도 각각의 표지판을 따로 세기로 합니다.

코드 ( C++ ) 종만북 참조

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int N,  K;

int L[5000], M[5000], G[5000];

const int INF = 987654321;

// 시작점부터 x 미터까지 K개 이상 표지판을 만날 수 있나?

bool decision(int x)

{

int ret = 0;

for (int i = 0; i < N; ++i)

{

if (x >= L[i] - M[i])

ret += (min(x, L[i]) - (L[i] - M[i])) / G[i] + 1;

}

return ret >= K;

}

int best = 987654321;

void optimize()

{

int lo = -1, hi = 8030001;

while (lo <= hi)

{

int mid = (lo + hi) / 2;

if (decision(mid)) {

best = min(best, mid);

hi = mid - 1;

}

else

lo = mid + 1;

}

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

int T;

cin >> T;

while (T--)

{

best = INF;

cin >> N >> K;

for (int i = 0; i < N; ++i)

{

cin >> L[i] >> M[i] >> G[i];

}

optimize();

cout << best << "\n";

}

}