종이를 접는 과정을 시뮬레이션하는 것이 너무 어려워서 종이접기의 결과를 어떻게 단순히 표현할 수 있을지 생각하게 되었습니다. 완벽하게 접힌 ($1$부터 $N$까지 순서대로 나열된) 종이는 위쪽에서 바라보았을 때 각 숫자마다 왼쪽, 오른쪽, 혹은 둘 모두의 접힌 면을 가지고 있습니다. 접힌 면으로 연결된 숫자들을 접힌 면의 방향을 고려하여 선으로 이으면 두 가지 규칙을 발견할 수 있습니다. 연속한 숫자가 같은 편의 선을 가질 수 없다. 예를 들어 1-2가 오른쪽 접힌 면을 가지고, 2-3이 다시 오른쪽으로 접힌 면을 가지는 상황은 발생할 수 없습니다....
$$z \equiv y \pmod x$$ 위 식을 만족하는 $a \le z \le b$를 찾는 문제입니다. $a = px + r \left(0 \le r \lt \lvert x\rvert\right)$로 두면, 두 가지 경우로 나누어 볼 수 있습니다. $y \ge r$ $px + y \le b$이면 $z = px + y$입니다. $px + \lvert x\rvert + y \le b$이면 답이 하나로 정해지지 않습니다. $y \lt r$ $px + \lvert x\rvert + y \le b$이면 $z = p + \lvert x\rvert + y$입니다....
현재 건물까지 건설하려면 이전 건물을 모두 지어야 합니다. $i$번째 건물까지 짓는 시간을 $\mathrm{total}\left(i\right)$, $i$번째 건물을 짓는 데 걸리는 시간을 $t_i$, $i$번째 건물 이전에 지어야 하는 건물들의 번호 집합을 $\mathcal{D}_i$라 하면 $$ \mathrm{total}\left(i\right)=\begin{cases} t_i & \left(\mathcal{D}_i = \varnothing\right) \\ t_i + \underset{j\in\mathcal{D}_i}{\mathrm{max}}\left(t_j\right) & \mathrm{otherwise.} \end{cases} $$ 따라서 각 건물을 깊이 우선 탐색하면서 $\mathrm{total}\left(i\right)$의 값을 저장해 두는 동적 계획법 풀이를 생각할 수 있습니다. 최댓값을 계산하기 위해 모든 건설 순서 규칙을 최대 한 번씩만 확인하므로 시간복잡도는 $O\left(K\right)$입니다....
2022-04-10 수정: 속도 비교 내용을 제거하고 입출력 방법에 대한 서술을 늘렸습니다. 입출력 Rust는 콘솔 입출력이 결코 편하다고 말할 수는 없는 환경입니다. 또한 잘못 짰을 경우 성능에 많은 저하가 있을 수 있기 때문에, 문제 풀이에 방해되지 않도록 빠른 입출력 방법을 찾을 필요가 있었습니다. Rust 입출력의 속도 저하 다음은 백준 Rust 예시에서 보여주는 코드입니다. 이 코드 그대로 문제 풀이를 진행한다면 많은 문제에서 시간 초과를 받을 수 있습니다. use std::io; fn main() { let mut s = String::new(); io::stdin()....
힌트 $i$번째 교환 후 $A$의 특정 범위의 값을 알 수 있습니다. 핵심 아이디어 선택 정렬은 문제 설명과 같이 최댓값을 한 번 찾고, 교환을 최대 한 번 하는 동작을 $N - 1$번만 반복합니다. 특히, $i$번째 교환에서 마지막 $i$개의 값이 모두 정렬됩니다. 알고리즘 이미 정렬된 배열과 뒤쪽 위치부터 비교하여 제자리에 있지 않은 값을 옮겨 주는 동작을 반복하는 식으로 문제를 해결할 수 있습니다. 먼저 각 수의 처음 위치를 각 수의 크기 순으로 배열 $S$에 저장하고, 뒤부터 탐색하면서 $S[i]$가 $i$가 아니라면 (즉 숫자가 제자리에 있지 않다면) $A$에서 $S[i]$번째 수와 i번째 수를 바꿔야 합니다....
좌표평면에서의 최소 신장 트리를 구성하는 문제입니다. 간선이 $\begin{pmatrix} n \\ 2 \end{pmatrix}$개이기 때문에 모든 간선을 저장할 수는 없고, 후보를 추려야 합니다. 간선의 가중치가 $\min\{|\Delta x|, |\Delta y|, |\Delta z|\}$이므로 x축, y축, z축 기준으로 정렬한 다음에 인접한 정점 사이의 간선을 확인하는 방법을 떠올릴 수 있습니다. 이후는 크루스칼 알고리즘을 통해 최소 신장 트리를 구성하면 됩니다. 여기서 “축 방향으로 인접한 정점 외에 다른 정점이 있는 경우를 제외하였다"라는 점이 의심스럽습니다. 이때에도 최소 신장 트리가 만들어진다는 것을 증명하려면, 축 방향으로 인접한 정점만으로 구성된 최소 신장 트리가 존재한다는 것만 보이면 됩니다....