전체 글 썸네일형 리스트형 BOJ)8217 유성 문제: icpc.me/8217 회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다. 각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다. 이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다. 따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자. 우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다... 더보기 BOJ)14434 놀이기구1 문제: icpc.me/14434 놀이기구를 타는 키 제한이 존재하고 각 날마다 키가 자라는 아이와 어떤 놀이기구를 타는지 물어보는 질의들이 주어질 때 각 날마다 아이들이 타는 놀이기구의 수를 출력하는 문제이다. 이 문제는 각 질의에 대하여 해당 놀이기구를 탈 수 있는 첫번 째 날을 구해주면 그 날 이후는 해당 놀이기구를 항상 탈 수 있으니 psum으로 해결 가능하다. 문제는 질의마다 첫번 째 놀이기구의 탑승 가능일을 구해주는 일이다. 우선 질의에 대해 첫번 째 놀이기구의 탑승 가능일을 탐색해야하므로 mid값을 날짜로 생각을 하자. 그럼 mid일에 놀이기구를 타야하는 두 아이의 키를 가져와야 하는데 이는 2차원 벡터로 각 아이에 대해 키가 크는 날짜를 벡터에 삽입해준다면 upper_bound로 계산해줄 수.. 더보기 BOJ)1396 크루스칼의 공 문제: icpc.me/1396 lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다. x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다. 오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다. MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다. 즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다. 예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5)) 여기서 새로 생기.. 더보기 이전 1 ··· 33 34 35 36 37 38 39 ··· 118 다음
