https://www.acmicpc.net/problem/3997 3997번: 하이퍼드롬 첫 번쨰 예제의 경우에 6개의 하이퍼드롬이 있다. - (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3). 두 번째 예제의 경우에는 12개가 있다. - (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (1, 3), (3, 5), (5, 7), (2, 6) www.acmicpc.net 문제를 읽어보면 조건들은 아래와 같습니다. 1. 대소문자 알파벳으로 이루어진 문자열이 주어짐 2. 문자열의 알파벳들을 적절히 바꿔서 팰린드롬을 만들 수 있다면 하이퍼드롬이라고 함 3. 그러면 문자열이 주어졌을 때, 연속된 부분 문자열들 중에서 하이퍼드롬인..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 읽어보면 이 문제의 조건은 아래와 같습니다. 1. 숫자들이 순서대로 주어질때, 중앙값을 계속 출력 2. 짝수개가 있으면 좀 더 작은 걸 선택 꽤나 조건이 간단하고 명확합니다. 이 문제를 처음 보았을 때 저는 매우매우 비슷한 문제를 푼 이력이 있어서 쉽게 결론에 도달하였습니다. 바로, Priority Queue를 두 개를 사용하는 방법입니다. Priority Queue가 왜 갑자기 ..

https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 문제를 읽어보면 조건은 아래와 같습니다. 1. x축 좌표상에 N개의 점이 주어져 있으며 각 점에는 가중치가 존재함 2. 그러면 Q개의 쿼리에서 x축 좌표가 하나 주어졌을 때, 각 점에서의 (거리 * 해당 점의 가중치)를 모두 더한 값을 구해야 함 저는 이 문제보고 처음에는 세그먼트 트리를 활용하는 문제인가 싶었습니다. 왜냐하면, N과 Q의 범위를 보았을 때, 결국에는 ..

https://www.acmicpc.net/problem/28296 28296번: 물류창고 UCPC시에는 $N$개의 물류창고가 있으며, $K$개의 회사가 각 물류창고를 소유하고 있다. 물류창고에는 $1$번부터 $N$번까지 차례대로 번호가 붙어있으며, 회사 또한 $1$번부터 $K$번까지 차례대로 번호 www.acmicpc.net 문제를 읽어보면, 문제의 조건들은 아래와 같습니다. 1. N개의 창고들이 있으며 창고 쌍에 대해서 잇는 간선들도 존재함 2. 간선들은 두 창고 쌍에 대해서 배송 상한선이라는 cost도 가지고 있음 3. 각 창고는 K개의 회사 중 하나에 속해있으며, 창고와 창고간의 배송 상한선은 이동 경로중의 배송 상한선이 제일 작은 간선의 배송 상한선이 됨 4. 여러 경로가 있으면 그 중 배송 상..

https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 일단 문제 조건을 읽어보자면 아래와 같습니다. 1. MooTube의 유사도는 트리 형태 2. 한 영상에서 다른 영상까지 갈려면 경로가 딱 한 가지 밖에 없음 3. 영상 쌍에 대한 유사도는 경로 중 최소 비용의 간선 4. 쿼리에서는 특정 영상과의 유사도가 k 이상인 영상들이 몇 개나 있는지를 물어봄 그리고 이를 읽고나서 저는 처음으로 들었던 생각은 이..