12.4_캐나다 여행_CANADATRIP

문제 설명

algospot.com :: CANADATRIP

• N개의 도시가 주어진다.(1 <=  N <= 5000)
• 각 도시의 위치를 L, 도시까지의 남은 거리를 표지판으로 M미터 전부터 G미터 간격마다 표시한다.(1 <= G <= M <= L = 8,030,000)
• M은 항상 G의 배수이다.
• K값이 주어진다.(1 <= K <= 2^31-1)

=> K번째 표지판의 위치를 출력하기

 

문제 풀이

결정문제로 바꾸기

K번째 표지판을 찾기에는 표지판의 위치가 도시마다 제각각이다.

그래서 "K번째 표지판의 위치 찾기" -> "어떤 dist 거리 까지의 표지판의 개수가 K보다 클까? 작을까?" 라는 결정문제로 바꾸어 생각했다.

 

각 도시가 가지는 정보

각 도시의 정보로 구할 수 있는 값은 다음과 같다.

• L : 도시의 위치
• M : 표지판이 시작되는 도시기준 상대위치
• G : 표지판이 배치되는 간격
• S : 표지판이 시작되는 절대 위치
• C : 표지판의 개수

L, M, G는 문제에서 주어지지만, S는 L-M으로, C 는 M / G + 1으로 구할 수 있다.

 

특정거리까지의 표지판 개수 구하기

특정 거리가 dist라면 각 도시와 dist거리까지의 관계는 다음 세 가지의 경우로 발생한다.

1. 도시 위치가 dist보다 앞에 있는 경우(L <= dist)
2. 도시의 표지판이 시작되는 지점과 도시의 위치 사이에 있는 경우(S <= dist < L)
3. 도시의 표지판이 시작되는 지점보다 dist가 앞에 있는 경우(dist < S)

1번의 경우라면 해당 도시의 표지판 개수(C)가 전부 세어질 것이다.

2번의 경우라면 dist부터 표지판이 시작되는 지점(S) 사이에 있는 표지판의 개수가 세어질 것이다.

3번의 경우라면 표지판이 세어지지 않는다.

 

이분 탐색

이분탐색으로 시간을 단축시킬 수 있다.

dist 기준으로 세어진 표지판의 개수가 K보다 크다면 더 작은 dist값으로,

dist 기준으로 세어진 표지판의 개수가 K보다 작다면 더 큰 dist값으로

바꾸어가면서 K개가 세어지는 dist값을 구하면 된다.

 

문제 풀이 코드

#include <iostream>

#define MAX(a,b)(a > b ? a : b)
#define MIN(a,b)(a < b ? a : b)

using namespace std;

struct City {
	int L, M, G, S, C;	// L, M, G, Start, Count
};

int N, K;
City cities[5000];

int countSign(int dist) {	// dist 까지의 표지판 개수 세기
	int count = 0;
	for (int i = 0; i < N; ++i) {
		if (cities[i].L <= dist) {	// 도시의 위치가 dist보다 앞에 있다면
			count += cities[i].C;
		}
		else if (cities[i].S <= dist) {	// 표지판의 시작점이 dist보다 앞에 있다면
			count += (dist - cities[i].S) / cities[i].G + 1;
		}
	}
	return count;
}

int solve(int startDist, int endDist) {	// 이분탐색
	if (startDist >= endDist) {
		return startDist;
	}
	int min = (startDist + endDist) / 2;
	int count = countSign(min);
	if (count >= K) return solve(startDist, min);
	return solve(min + 1, endDist);
}

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

	int T;
	cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> N >> K;
		int startDist = 8030000;
		int endDist = 1;
		for (int i = 0; i < N; ++i) {
			cin >> cities[i].L >> cities[i].M >> cities[i].G;
			cities[i].S = cities[i].L - cities[i].M;		// 표지판 시작 위치
			cities[i].C = cities[i].M / cities[i].G + 1;	// 표지판의 개수
			startDist = MIN(cities[i].S, startDist);
			endDist = MAX(cities[i].L, endDist);
		}
		cout << solve(startDist, endDist) << endl;
	}
}