https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 우선순위 큐와 구현 문제다. 우선순위 큐에 입력 받은 값을 넣어 오름차순으로 정렬되게끔 했다. 2차원 배열을 이용해서 컴퓨터 사용이 끝나는 시간과 몇 명이 이용했는지 저장했다. 반복문으로 컴퓨터를 사용하지 않았거나, 사용 기록이 있으나 이미 퇴실한 자리를 찾아 저장했다. #include #include using..
우선순위 큐
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선수위 큐와 그리디 문제다. 처음에는 작은 수가 여러 번 더해지는 게 최솟값이 나올 거라고 생각해 정렬 후 각 수에 n - i를 곱해서 더하는 방법을 생각했다. 이 방법은 항상 앞의 두 수 합에 바로 뒤에 숫자를 더한다. 반례가 있을 것 같다는 생각이 들었다. (a + b) (c + d) e 를 더하는 것이 최솟값이 나오는 경우가 있을 것 같았다. 있었다. 원소 삽입마다 정렬이 되..
