펜윅 트리 썸네일형 리스트형 BOJ)8217 유성 문제: icpc.me/8217 회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다. 각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다. 이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다. 따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자. 우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다... 더보기 이전 1 다음