오프라인 쿼리 썸네일형 리스트형 BOJ)15745 Snow Boots 문제: icpc.me/15745 1~N 영역에 쌓인 눈의 높이가 주어진다. 이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다. i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다. 풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다. 우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다. 쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로 역순으로 쿼리를 처리하면서, 못넘는.. 더보기 이전 1 다음