algospot 캐나다 여행 (문제 ID: CANADATRIP) C++

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/CANADATRIP

algospot.com :: CANADATRIP

각 도시마다 도시에 도착하기 거리 m전에 g간격으로 표지판들이 나열되어있다. 각 도시들의 갯수와 위치가 주어지고 도시들마다의 m과 g가 주어질때 k번째 표지판의 위치를 찾는 문제이다.

전체 거리가 8030000이기 때문에 완전탐색에는 무리가 있다.

해결 방법으로는 출발점부터 도착점까지 각각을 lo와 hi로 설정하고 이분법을 이용하여 중간지점까지 갔을때 지나친 표지판의 갯수를 계산하는 것이다.

만약 계산한 표지판의 갯수가 k보다 적으면 lo를 높이고 많으면 hi를 낮추면 된다.

표지판의 갯수를 셀때는 출발점부터 해당지점까지와 각 도시들의 표지판이 놓여져 있는 영역들의 겹치는 부분을 계산해서 g로 나누고 +1 해주면 된다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/CANADATRIP.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1