kth990303의 코딩 블로그

백준 초급스터디에 과제로 내준 문제인데, 생각보다 어려워보이는 문제여서 한 번 풀어보았다. KOI (정보올림피아드) 2018 고등부 2번 문제이기도 하다. 일단 비주얼부터 한 번 감상해보자. 비주얼이 거의 수능수학 문제를 뺨친다. 문제는 아래와 같다. https://www.acmicpc.net/problem/15976 15976번: XCorr $ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다. www.acmicpc.net 문제가 조금 헷갈릴 수 있는데, 입력에 주어지지 않은 xi, yi는 0이라고 생각하면 된다. 의식의 흐름 및 해설 우리가 구하려는 것을 다시 한 번 살펴보자. 으... 정말 비주얼이 끔찍하다. 일단 a..

개인적으로 꽤 어렵게 느껴졌기 때문에 풀고난 후 티어를 보고 깜짝 놀랐다. 내가 정점/간선 인덱스를 헷갈리게 하는 유형에 약해서 그런진 모르겠지만, 나는 G1~P5 급이라 생각한다. 하지만 그만큼 배울점도 많았던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/20553 20553번: 다오와 디지니의 데이트 첫 줄에 두 정수 $N$과 $T$가 주어진다. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$) 두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 수는 $h_i$를 의미한다. ($-10^9 \le h_i \le 10^9$, $h_1 = 0$) www.acmicpc.net 얘들아 근데 너네 데이트는 어떻게 하니..

KOI 2차대회 중등부 문제이다. 예상보다 꽤나 고전했던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 의식의 흐름 및 해설 범위가 상당히 크기 때문에 좌표 범위대로 스위핑은 불가능하다. 대신, N개의 좌표를 순서대로 스위핑은 가능하며, 주어진 q가 어느 마을 사이에 있는지 이분탐색으로 구해줄 수 있겠다. 이렇게 대충 O(QlgN) 시간복잡도를 떠올릴 수 있는데, 문제는 누적거리가 어떻..

괄호 문자열 시리즈 문제 중 하나이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 사실 괄호 문자열 문제가 시리즈로 있다는 것을 이 문제로 처음 알았다. 예전에 풀어본 9935번 문자열폭발 문제랑 비슷한 줄 알았는데, 생각해보니 그 문제는 괄호가 아니라 문자열 관련 문제였다. 괄호라고 해서 스택, 카탈란수가 생각나서 비슷하게 생각했나보다. 의식의 흐름 및 해설 처음에는 스택이나 카탈란 수를 떠올렸다. 그러..