leejseo의 블로그

문제 다음 링크 https://www.acmicpc.net/problem/10803 에서 문제를 확인할 수 있다. 해법 $D[i][j]$를 $i \times j$ 직사각형을 정사각형으로 나누었을 때, 나뉘게 되는 최소 갯수로 정의하자. 그러면, 다음의 점화식을 간단히 떠올릴 수 있다. $$D[i][j] = \begin{cases} 1 & \text{if } i = j \\ \min( \min_{k \le i/2} (D[k][j] + D[i-k][j]), \min_{k \le j/2} (D[i][k] + D[i][j-k]) ) & \text{otherwise} \end{cases}$$ 그런데, 이 알고리즘은 효율적이지 못해서 시간 제한 조건을 위반한다. 그런데, 조금 생각해 보면, i가 j에 비해 많이 큰..

문제의 경우 백준 온라인 저지에서 확인할 수 있다. 이 문제를 풀기 위해서는 BOI 2004에 출제되었던 문제 중 하나인 BOJ 2336 - 굉장한 학생을 풀어보면 좋다. 1. 굉장한 학생 풀이 굉장한 학생 문제는 세그먼트 트리의 구간 최솟값 쿼리(RMQ)를 이용하여 해결할 수 있다.각각의 $i = 1, 2, \dots, n$에 대하여 $x_i$, $y_i$, $z_i$를 각각 1,2,3번째 시험에서 $i$의 등수라 하자.학생들의 번호를 $x_i$가 증가하는 순서로 정렬해놓자.그러면 학생 $i$가 굉장하지 않을 필요충분조건은 어떤 $k$가 존재해 $x_k < x_i \land y_k < y_i \land z_k < z_i$인 것이고, 학생들의 번호가 정렬되어 있으므로 어떤 $k < i$에 대해 $y_k ..

문제 디스크립션과 템플릿 파일의 경우 본문 하단에 첨부되어 있다. 간단한 분석을 통해 해결할 수 있다. 바로 만점 풀이를 설명하자면, 첫 글자를 2개의 쿼리를 통해 결정하고, 가운데의 $N-2$ 글자를 $N-2$개의 쿼리를 통해 결정한 후, 마지막 글자를 2개의 쿼리를 통해 결정하면 된다. Step 1. 첫 글자 결정하기"AB"와 "AX", 이 두 가지 문자열에 대한 질의를 통해 첫 글자를 결정할 수 있다.그 이유는, 두 개의 질의 모두 1 이상의 답변을 받았을 경우 첫 글자는 A이며, 모두 0인 경우 첫 글자는 Y이다.아니라면, "AB"에 대한 답변이 1일 경우 첫 글자는 B이며, 이도 아니라면 첫 글자는 X이다. Step 2. 가운데 글자 결정하기일반성을 잃지 않고 첫 글자를 A로 가정하자.구하는 문..

문제의 경우 링크에서 확인할 수 있다. 풀이. 리프 노드 $i = 1, 2, \cdots , N$에 대하여 $S_i$를 계통 그래프 상에서 $i$에 인접한 정점들의 집합으로 정의하자. 문제의 조건으로 부터 다음의 사실들을 쉽게 확인할 수 있다.같은 부모 노드에 연결된 리프 노드들은 계통 그래프 상에서 클릭(완전 그래프인 부분 그래프)을 이룬다같은 부모 노드에 연결된 두 리프 노드 $i, j$는 $S_i \cup \{i \} = S_j \cup \{ j \}$를 만족시킨다.두 리프 노드의 부모 노드가 다르다면, 이들이 계통 그래프 상에서 인접할 필요 충분 조건은 이들의 부모 노드가 인접한 것이다.계통 그래프에서 연결 상태가 같은 노드들을 각각 하나의 그룹으로 묶어주자. 그러면, 1과 2에 의해 두 리프 노..

문제의 경우 KSA Online Judge 또는 oj.uz 에서 확인할 수 있고, 채점 또한 가능합니다. 풀이 개요대회장에서는 부분점수만 일부 받았고, 현재 올리는 풀이는 BOJ 슬랙에서 지나가다가 우연히 봤던 풀이입니다. (누가 올렸던 것인지는 기억이 안나네요... 본지 너무 오래되어서 오늘 코드 짜보는데도 std::set 을 관리한다는 것만 기억났네요..) 이 문제에서 가장 핵심적인 부분은 첫 번째 행의 원소들을 기준으로 각각의 열들을 정렬하는 것입니다. 그러고 나면, 이 문제는 2차원 상의 점 $N$개에 대해 가장 긴 증가하는 부분수열을 구하는 것으로 환원됩니다. 첫 번째 행의 원소들의 '등수'를 index로 하고, 2, 3번째 행의 원소들을 2차원 상의 점으로 하는 '점들의 수열'을 생각합시다. ..

고등부 1번 화살표 그리기채점은 https://ksa-oj.ml/problem/koi18h1 에서 가능합니다. 각각의 점은 같은 색깔의 점 중 자신의 바로 왼쪽에 있는 점 또는 자신의 바로 오른쪽에 있는 점과 연결됩니다. 따라서, 모두 정렬한 후, 전체 점들을 왼쪽으로 한 번, 오른쪽으로 한 번 훑어주면 총 $O(N \log N)$ 시간복잡도로 문제를 해결할 수 있습니다. C++을 이용한 구현은 아래와 같습니다. #include using namespace std; #define endl '\n' const int MAXN = 100000; typedef pair point; vector L; int A[MAXN], P[MAXN+1], N; int main(){ ios::sync_with_stdio(0)..

문제의 경우 다음 링크에서 확인할 수 있다. 접근 방법 및 풀이. 이 문제의 풀이는 간단하게도, 0번 문 부터 차례로 자신에 대응되는 스위치를 찾는데, 이분 탐색을 통해 '답의 후보'를 계속 절반으로 줄여나가는 것이다. 각각의 문에 대해 $13 = \lceil \log_2(5000) \rceil$번 만에 대응되는 스위치를 찾을 수 있고, 스위치의 '답'을 찾는데 1회의 시행이 필요하다. 이렇게 하면, 함수의 호출 횟수 제한을 지키면서 스위치의 조합을 찾을 수 있다. $14 \times 5,000 = 70,000$ 필자의 C++ 소스코드는 아래와 같다. #include "cave.h" #include using namespace std; vector L; int S[5001], D[5001]; bool D..

문제. 도시 $0$에서 도시 $N$으로 이동하고자 한다. 이 때, 각각의 $i=1,2,\cdots, N$에 대하여 도시 $i-1$에서 도시 $i$까지 이동하는 방법으로는 걷거나/자전거를 타는 2가지의 방법이 있다. 각각의 이동 방법에 대해 소요시간/버는 돈이 정해져 있다. 이 때, 도시 $N$까지 $K$시간 이내에 이동하면서 벌 수 있는 최대 금액을 구하여라. (단, $3\leq N \leq 100$, $0 \leq K \leq 100,000$이다.) 채점 사이트 링크: http://icpc.me/14863 풀이. $O(NK)$ 알고리즘으로 해결할 경우, 시간 제한 조건을 위반하지 않습니다. 그런데, 잘 생각해 보면, 이 문제는 냅색 문제와 비슷한 형태를 가지고 있음을 알 수 있습니다. 따라서 $$D[i..

이 문제를 채점하고자 한다면 http://icpc.me/14864로 이동하시면 됩니다. 문제의 내용을 요약하자면, 반전의 쌍들이 주어졌을때, 실제로 그 쌍들만을 정확히 자신의 반전으로 가지는 순열이 존재하는지 판별하고, 존재한다면 찾으라는 문제입니다. 이 문제를 조금 분석하자면, $\bf (x, y)$와 같이 반전들이 주어지기 때문에, 이 정보를 활용해, 우리가 찾는 순열이 $\sigma$라고 할 때, 각각의 $1 \leq i \leq N$에 대하여 다음의 성립함을 확인할 수 있습니다:- $t < i$이고, $\sigma(t) < \sigma(i)$인 $t$의 수: $(i-1) -(\bf y$자리에 $i$가 오는 순서쌍의 수$)$- $t > i$이고, $\sigma(t) > \sigma(i)$인 $t$의..

문제의 경우 https://www.acmicpc.net/problem/13310 에서 확인할 수 있다. 풀이.이 문제의 경우 모든 부분문제를 해결하기 위해서는 $O(N \log N \log T)$ 알고리즘이 요구되며, 이것은 다음의 두 단계를 거쳐 설계할 수 있다. 먼저, $k$개의 함수 $f_i : \mathbb{R} \rightarrow \mathbb{R} (1 \leq i \leq k)$이 모두 아래로 볼록한 함수이면, $f:\mathbb{R} \rightarrow \mathbb{R}$; $f(x) =$ $\max \left \{ f_i (x) | 1 \leq i \leq k \right \}$로 정의된 함수 $f$ 또한 아래로 볼록한 함수임을 알 수 있다. 이제, $g:\mathbb{R} \rig..