본문 바로가기

전체 글

BOJ)15745 Snow Boots 문제: icpc.me/15745 1~N 영역에 쌓인 눈의 높이가 주어진다. 이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다. i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다. 풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다. 우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다. 쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로 역순으로 쿼리를 처리하면서, 못넘는.. 더보기
BOJ)13274 수열 문제: icpc.me/13274 정렬 된 수열에서 쿼리를 처리하는 문제이다. 쿼리 l r x 는 l~r 구간의 원소에 x를 더해준 뒤 다시 정렬하는 쿼리이다. n이 10만이고 쿼리가 1000개 인데 매번 퀵소트를 실행해주면 1억xlog10만 이므로 1초의 제한 시간에 간당간당한 느낌이다. 따라서 좀 더 빠른 소팅 방법이 필요한데, 정렬 된 구간에서 l~r에 x를 더하게 되면, l~r의 구간은 오름차순을 유지할 것이며, 전체의 구간에서 l~r의 구간을 제외한 구간 역시 오름차순을 유지할 것이다. 이렇게 정렬 된 두 구간에서 서로 가장 앞 원소를 비교하며 insertion sort를 하면 소팅을 O(N)의 시간에 해결할 수 있다. 1234567891011121314151617181920212223242526.. 더보기
BOJ)15589 Lifeguards (Silver) 문제: icpc.me/15589 n명의 인원이 1차원 구간을 커버하는 데 이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다. 전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로 하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다. 각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 자세한 설명은 소스코드로 대신하겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace s.. 더보기