구사과

원래 한 150점 어치 풀이를 적어놓은 게 있었는데, 포맷하다가 글이 사라져서 더 이상 글을 쓰고 싶지 않았다. 그래도 아예 안 적을 수는 없으니 늦게나마 글을 작성해 본다. A. 육각형 영역 문제 번역을 담당해 주신 교수님이 문제 주인공에 제 이름을 넣어주셨습니다 (감사합니다!). 그와 별개로 전 이 똥문제에 대해 아무 책임이 없음을 밝힙니다 (...) 서브태스크 2 (9점) 영역의 형태가 항상 정삼각형이다. 거리가 $d$ 인 점의 개수가 $d+1$ 개라는 점을 사용하면 문제의 답을 적절한 수식으로 표현할 수 있다. $\sum n, \sum n^2$ 를 공식을 사용하여 $O(1)$ 에 계산하면 전체 문제가 $O(1)$ 에 풀린다. 서브태스크 3 (20점) 육각 격자를 컴퓨터에서 다루는 가장 편한 방법은..

https://www.acmicpc.net/problem/19021 트리를 DFS하면서, 노드의 방문을 시작한 시점에 (, 끝내는 시점에 ) 를 붙이는 식으로 올바른 괄호 문자열을 만들어 줄 수 있습니다. 주어진 입력을 트리가 아니라 괄호 문자열이라고 생각하면 1, 2번 연산은 짝이 맞는 괄호 쌍을 추가하는 것이고 3번 연산은 짝이 맞는 괄호 쌍을 제거하는 것 으로 볼 수 있습니다. Edit Distance와 LCS의 관계처럼, 두 괄호 문자열의 최대 공통 부분 괄호 문자열을 찾아 줍시다. $T_1$ 의 모든 괄호를 제거 / $T_2$ 의 모든 괄호를 추가하는 비용을 미리 지불했다고 하면, 두 괄호 $A, B$ 를 매치했을 때의 비용은 $C_3 \times \text{(A, B를 매칭하는 데 드는 비용)..

https://www.acmicpc.net/problem/19616 모든 상태를 중 가중치가 가장 작은 $K$ 개를 탐색할 때 좋은 전략은, 상태 전이 그래프를 Heap과 같이 구성하는 것입니다. 몇 가지 특수 케이스를 탐색해 보고 전체 문제로 확장시켜 봅시다. $M = 1, x_1 = 0, y_1 = N$, 제곱 풀이 우리는 모든 가능한 $2^N$ 개의 집합 중 가중치가 가장 작은 $K$ 개를 탐색해야 합니다. 탐색 트리를 만드는데, 만약에 모든 상태가 가능한 집합에 일대일 대응되고 상태 $X$ 의 자식은 항상 현재 상태 이상의 가중치를 가지며 전이가 트리의 형태를 띈다 라고 하면, 루트 상태를 먼저 우선순위 큐에 넣은 후, 큐에서 현재 상태를 빼고, 현재 상태의 "자식 상태" 를 넣는 식으로 모든 가..