우선순위 큐2 BOJ 13549 숨바꼭질 3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 2와 다르게 3은 cur * 2 지점으로 텔레포트할 때에 시간이 소요되지 않는다. 평범하게 큐로 bfs 할 경우 기존 cur -1, cur + 1을 하면서 K에 도착하게 되면 이후에 cur * 2 를 통해 도착하는 시간보다 더 크지만 이미 방문처리가 되어있으므로 값을 갱신시켜줄 수 없다. 어떻게 접근해야될까? 이 문제는 우선순위 큐를 최소 힙으로 선언한 후 time을 .. 2020. 12. 28. BOJ 11000 강의실 배정 www.acmicpc.net/problem/1100011000번: 강의실 배정첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)www.acmicpc.net강의실 배정 문제다. 어떻게 하면 최대한 적은 강의실을 사용해서 모든 강의를 할 것인지를 찾아내면 된다.처음에는 회의실 배정 문제랑 비슷한 문제인 것 같아서 강의 종료 시점을 기준으로 정렬해서 제출했는데 틀렸다.찾아보니 priority_queue를 사용해서 시작시간을 기준으로 해결해야 한다.큐는 최소 힙으로 선언해주고 큐에는 종료시간만 삽입한다. 대략적인 접근방법은 이렇다.벡터에 pair로 시작시간, 종료시간을 입력받는다시작시간을 기준으로 정렬하고 priority_.. 2020. 10. 2. 이전 1 다음
