Level 2. 디펜스 게임 정답이 몇 라운드가 되던지, 그 중 무적권을 사용한 라운드는 가장 몬스터가 많이 나오는 n개여야 하므로 우선순위 큐를 사용해야 할 것 같았다. 이번 문제는 솔직히 당연히 틀릴 줄 알고 제출했는데 정답 처리돼서 당황스러웠다. 무적권을 사용할 수 있으면 일단 사용하고 최소힙에 넣는다. 이후 무적권이 없을 때부터는 최소힙의 최솟값과 현재 라운드의 몬스터 수를 비교해, 이전에 썼던 것보다 현재 라운드에 쓰는 게 이득이면 이전 라운드의 몬스터 수를 n에서 빼고 현재 라운드에 무적권을 사용한다. 나중에 현재 라운드에 사용한 것보다 이득인 상황이 올 수 있으므로, 현재 라운드의 몬스터 수도 최소힙에 넣어 주어야 한다. 현재 라운드보다 이전에 썼던 것이 이득이면, 현재 라운드의 몬스터 수를..

Level 3. 단속카메라 여러 개의 구간이 주어진 문제라면, 일단 시작점을 기준으로 정렬할 생각부터 해야 한다. 이 문제에서는 최소힙을 구성하기 위해 Section의 < 연산자를 반대로 오버로딩했다. set, map 등과 달리 우선순위 큐는 최대힙이 기본이기 때문이다. 별도 관리하는 끝점과 각 구간의 시작점을 비교하므로, 끝점은 정렬하지 않아도 된다. 현재 단속 카메라를 배치할 수 있는 끝점을 end 변수로 관리하고, end보다 큰 시작점이 나오면 새로운 카메라를 배치해야 한다. end보다 작거나 같은 시작점이 나오면 현재 카메라를 공유할 수 있다는 뜻인데, 이 때도 가능한 작은 위치에 카메라를 배치해 더 많은 카메라를 공유할 수 있도록 갱신해야 한다. #include #include #include ..

Level 3. 입국심사 도저히 이 문제가 왜 이분 탐색 문제인지 감이 안 잡혀서 찾아보았다. 이분 탐색 문제는 입력의 크기가 매우 큰데 하나의 답을 찾아야 하는 것이 특징이다. 포인트는 사람 수가 아닌, 시간을 중심으로 이분 탐색을 진행해 답을 찾는다는 것이었다. 가장 오래 걸리는 심사관에게 모두 심사를 받는 경우를 최악의 경우로 설정한다. 이분 탐색을 진행할 때마다 주어진 시간 동안 모든 사람이 심사를 받을 수 있는지 확인한다. 각 (주어진 시간 / 심사 시간)을 합한 값이 심사할 수 있는 사람의 수라는데 처음엔 왜 이렇게 되는지 이해가 되지 않았다. 하지만, 사람이 아니라 각 심사관을 중심으로 생각해보면 실제로 그렇다. #include #include #include using namespace s..

Level 2. 택배상자 스택을 활용한 간단한 시뮬레이션 문제다. 그냥 매번 보조 벨트에 넣고, 뺄 때는 보조 벨트에서만 빼면 된다. #include #include #include using namespace std; int solution(vector order) { int answer = 0; size_t n = order.size(); stack stck; for (int i = 1; i

Level 3. 합승 택시 요금 플로이드-워셜 알고리즘을 응용하는 문제다. 모든 점들 간의 최단 거리를 구해야 할 때 사용한다. 3중 for문을 이용하는 O(n³) 시간 복잡도 때문에, 정점의 개수가 200개 미만으로 적은 것이 특징이다. 초기화 시 ∞를 무조건 INT_MAX로 설정하면, 더할 때 음수가 돼버리므로 주의해야 한다. 우선 모든 점들 간의 최단 거리를 구한 후, (S → I 비용) + (I → A 비용) + (I → B 비용)이 S에서 I까지 합승 후 각자 집으로 간 비용이다. 이 값들의 최솟값을 구하면 된다. #include #include #include #define UNREACHABLE 19'900'000 using namespace std; int solution(int n, int..

Level 2. 카카오프렌즈 컬러링북 전형적인 완전 탐색 문제다. DFS가 깔끔해서 썼지만 BFS로 풀 수도 있다. #include #include #include using namespace std; int rDFS(unsigned i, unsigned j, int color, vector& picture) { if (picture.size()