김상조의 블로그

https://www.acmicpc.net/problem/1826

1L에 1km씩 갈 수 있고, 목적지까지 갈 수 있냐의 문제.

N 이 10000밖에 되질 않아서 DP로도 풀린다.

그리디는 글쎄 생각이 나질 않는다.

이 문제는 우선순위 큐로 풀었는데,

우선 주유소를 거리를 기준으로 sort하고(문제가 약았다)

내가 갈 수 있는 범위 내의 주유소의 기름을 max heap에 다가 넣어 준다.

그리고 max heap의 첫 번째의 기름을 더해서 내가 갈 수 있는 범위를 늘리며, 

그 기름양은 pop해준다.

그 범위 안에 있는 모든 주유소의 기름양을 max heap에 넣는다.

그리고 다시 max heap 첫 번 째 기름을 더해서 내가 갈 수 있는 범위를 늘리며 그 기름양은 pop하는 것을 반복한다.

최종적으로 목적지의 거리만큼 나의 기름양이 누적되었으면, 성공! 기름을 더해준 횟수를 출력.

안되면 -1을 출력한다.

https://www.acmicpc.net/problem/1655

주어지는 입력을 소트한다고 했을 때, 그 중간 값을 뽑아내며, 

전체 짝수가 주어지면 중간 값 2개 중 더 작은 애를 뽑아내는 문제다.

이 문제를 해결하는 방법을 생각해보자.

먼저 드는 생각은 balanced tree를 만들어 중간 위치를 찾으면 그만이다.

하지만, treap이나 red-black tree를 어느 세월에 만들어 낼 것인가....

문제의 유형처럼 heap으로 해결해보자.

heap으로 해결하는 방법이 선뜻 떠오르지 않는다.

먼저 2개의 heap을 만들어 낸다.

maxHeap과 minHeap인데

주어진 수열을 sort한 다음, 앞 절반을 maxHeap에,  뒷 절반을 minHeap에 넣으면 

다음 2가지 성질이 성립된다.

1. maxHeap의 size는 minHeap size보다 같거나 1크다.

2. maxHeap의 첫 원소는 minHeap의 첫 원소보다 작거나 같다.

자 input이 주어지면, 

input을 maxHeap, minHeap 번갈아서 넣는다. maxHeap 먼저.

그리고 maxHeap의 첫 원소와 minHeap의 첫 원소를 비교해서

maxHeap이 더 크면, 2개의 위치를 바꾸어준다.