티스토리 뷰
D
이 문제는 양의 정수 $N$이 주어질 때, 두 개의 양의 정수 $(x, y)$가 존재하여 $x^3 - y^3 = N$을 만족하는지 확인하는 문제이다. 존재하는 경우, 해당 $(x, y)$ 쌍을 출력하고, 존재하지 않는 경우 $-1$을 출력해야 한다. 가능한 여러 해 중 하나만 출력해도 된다.
해설
$x^3 - y^3 = N$에서 $x - y = d$라 두면 $x^3 - y^3 = d(x^2 + xy + y^2)$.
$x^2 + xy + y^2 \geq (x - y)^2 = d^2$이므로 $d^3 \leq d(x^2 + xy + y^2) = N$,
즉, $d \leq \sqrt[3]{N}$이다. 이제 $d$를 $1$부터 $\sqrt[3]{N}$까지 모두 탐색한다. $x = k + d, ; y = k$라 두면
$(k + d)^3 - k^3 = d^3 + 3d^2k + 3dk^2 = N$.
주어진 $d$에 대해 위 식은 $k$에 관한 이차 방정식으로 변형할 수 있다. 이 방정식을 정수 해 $k$에 대해 풀어, 해가 존재하면 $(x, y) = (k + d, k)$가 해가 된다. 만약 모든 $d$에 대해 적절한 $k$가 없으면 해가 존재하지 않으므로 $-1$을 출력한다. 이 방법은 $d$의 범위가 $O(\sqrt[3]{N})$이므로, 적절한 방법(예, 이차 방정식의 해를 구하거나 이진 탐색을 이용)으로 $k$를 찾으면 $O(\sqrt[3]{N})$ 또는 $O(\sqrt[3]{N} \log N)$ 시간에 문제를 해결할 수 있다. 구현 시 오버플로우에 주의해야 한다.
E
이 문제는 정점 개수가 $NK$인 트리가 주어졌을 때, 이를 길이가 $K$인 $N$개의 경로로 분할할 수 있는지 판별하는 문제이다.
즉, $N \times K$ 행렬 $P$가 존재하여:
- $P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K}$가 $1, 2, \dots, NK$의 순열이 되며,
- 각 행에서 연속한 두 정점 $P_{i,j}$와 $P_{i,j+1}$이 주어진 트리에서 연결되어야 한다.
가능하면 "Yes", 불가능하면 "No"를 출력한다.
해설
- 핵심 아이디어:
트리 $T$를 경로들로 분해할 수 있으려면, 모든 $K$-정점 부분트리가 경로여야 하며, 경로인 $K$-정점 부분트리가 최소한 하나는 존재해야 한다.
따라서 “$K$-정점 부분트리가 경로라면 이를 제거하고, 모든 정점을 제거할 수 있는가?”를 판단하면 된다. - 트리 DP 접근법:
- 루트 설정 및 후위 순회:
정점 $1$을 루트로 삼고, 리프부터 올라오면서 각 정점 $v$에 대해 $T_v$에 속하는 정점의 수 $s_v$를 계산한다.
$s_v = (\text{자식들의 } s \text{ 합}) + 1$. - 세 가지 경우 분기 처리:
- $s_v < K$:
- $v$가 루트가 아니면, $T_v$와 $v$의 부모를 포함하는 어떠한 부분트리에도 $T_v$가 모두 포함된다.
- 만약 $v$의 자식 수 $c_v$가 $2$ 이상이면, $v$의 차수는 최소 $3$이 되어 경로가 될 수 없으므로 분해 불가능 → No.
- $s_v > K$:
- $T_v$ 내에 $K$-정점 부분트리가 존재하지 않으므로, 이 부분에서 경로 추출이 불가능 → No.
- $s_v = K$:
- $T_v$는 경로여야 한다.
- 만약 $v$의 자식 수 $c_v$가 $3$ 이상이면 경로가 아니므로 → No.
- $c_v$가 $2$ 이하라면 $T_v$는 경로가 맞으므로, $T_v$를 제거하기 위해 $s_v$를 $0$으로 갱신.
- $s_v < K$:
- 루트 설정 및 후위 순회:
- 최종 판단:
위 과정을 통해 모든 정점을 제거할 수 있다면 $T$는 경로들로 분해 가능하다.
제거 과정 중 한 번이라도 조건을 만족하지 못하면, $T$는 분해할 수 없음. - 시간 복잡도:
각 정점에 대해 최대 $K$개의 상태를 고려하므로 전체 시간 복잡도는 $O(NK)$.
F
이 문제는 길이 $N$인 정수 수열 $A$가 주어질 때, 이를 세 개의 연속한 부분 배열로 분할하여 각 부분 배열에서 서로 다른 원소의 개수의 합을 최대화하는 문제이다.
즉, $1 \leq i < j \leq N-1$인 두 개의 분할 위치 $(i, j)$를 선택하여:
- 첫 번째 부분 배열: $A_1, A_2, ..., A_i$
- 두 번째 부분 배열: $A_{i+1}, A_{i+2}, ..., A_j$
- 세 번째 부분 배열: $A_{j+1}, A_{j+2}, ..., A_N$
각 부분 배열에서 서로 다른 원소의 개수를 구한 후, 이들의 합을 최대로 만드는 경우를 찾는 것이 목표이다.
해설
주어진 배열 $A$를 두 개의 비어있지 않은 부분 배열로 나누었을 때, 두 부분에서의 서로 다른 원소 개수 합의 최댓값을 구하는 문제이다.
- 정의 및 접근법
- $L_i$ : 배열 $(A_1, A_2, \dots, A_i)$ 내의 서로 다른 원소의 개수
- $R_i$ : 배열 $(A_i, A_{i+1}, \dots, A_N)$ 내의 서로 다른 원소의 개수
- $X_i$ : 배열 $(A_1, A_2, \dots, A_i)$를 두 개의 부분 배열로 나눌 때 가능한 최대 합
- $L$과 $R$ 계산 (O(N))
- $L$은 앞에서부터, $R$은 뒤에서부터 순회하면서 각 숫자가 처음 등장했는지를 해시맵 등을 이용해 체크하면 $O(N)$에 계산할 수 있다.
- $X_i$ 계산 (O(N \log N))
- $dp_{i,j}$ : $A_1$부터 $A_i$까지 고려할 때, 두 부분 배열의 서로 다른 원소 개수의 합 중 최댓값
- $X_i = \max dp_{i,j}$
- 점화식: dpi+1,j={dpi,j+1if (Aj+1,…,Ai) 내에 Ai+1이 없으면dpi,jif (Aj+1,…,Ai) 내에 Ai+1이 있으면dp_{i+1, j} = \begin{cases} dp_{i,j} + 1 & \text{if } (A_{j+1}, \dots, A_i) \text{ 내에 } A_{i+1} \text{이 없으면} \\ dp_{i,j} & \text{if } (A_{j+1}, \dots, A_i) \text{ 내에 } A_{i+1} \text{이 있으면} \end{cases}
- $dp_{i+1, i} = L_i + 1$
- $j$가 증가하면서 $A_{i+1}$이 부분 배열에 포함되는 것은 단조적이므로, 세그먼트 트리의 구간 덧셈 (lazy propagation) + 구간 최대값 쿼리를 이용하면 $O(N \log N)$에 해결 가능.
- 최종 복잡도
- $L$과 $R$ 계산: $O(N)$
- $X_i$ 계산 (세그먼트 트리 사용): $O(N \log N)$
- 최종적으로 $O(N \log N)$에 문제를 해결할 수 있다.
G
이 문제는 $N$개의 정점과 $M$개의 간선을 가진 방향 그래프에서, 정점 1에서 정점 $N$까지의 최단 거리를 최대화하는 문제이다.
초기에 모든 간선의 가중치는 $0$이며, $M$개의 간선 중 정확히 $K$개를 선택하여 가중치를 $1$로 변경할 수 있다.
이후 변경된 그래프에서 정점 1에서 정점 $N$까지의 최단 경로의 길이의 최댓값을 구해야 한다.
해설
주어진 그래프에서 정점 $1$에서 정점 $N$까지의 최단 거리를 최소 $d$ 이상으로 만들기 위해 수정해야 하는 최소 간선 수를 구하는 문제이다.
이를 해결하기 위해 이진 탐색과 최소 컷 (Minimum Cut) 문제를 활용한다.
1. $d = 1$일 때의 최소 컷 문제
- 핵심 아이디어:
최단 거리가 $1$ 이상이 되려면, $1$에서 $N$까지 직접 연결된 간선을 제거해야 한다.
즉, 1에서 $N$까지의 모든 가중치 0인 경로를 차단해야 한다.
이는 1에서 $N$까지의 최소 컷(Minimum Cut) 값을 구하는 문제와 동일하다. - 풀이 방법:
- 그래프의 최소 컷을 Dinic 알고리즘 ($O(N^2 M)$)을 사용하여 구한다.
- 최소 컷이 $K$ 이하이면 가능, 그렇지 않으면 불가능하다.
2. 일반적인 $d$에 대한 접근
$d \geq 1$인 경우, 각 정점 $i$에 대해 변수를 $x_i$를 정의한다.
- $x_i$는 정점 $i$까지의 최단 거리 값을 나타내며, 값의 범위는 $[0, d]$이다.
- 각 간선 $(u,v)$에 대해 다음과 같이 비용을 정의한다:
- $x_u + 1 = x_v$인 경우 → 비용 1
- $x_u + 1 < x_v$인 경우 → 비용 $\infty$ (불가능한 이동)
3. $x_i$ 값을 0/1 변수로 변환
- 새로운 이진 변수 $y_{i,j}$를 정의하여 변환한다: $xi=j ⟺ yi,1=yi,2=⋯=yi,j=1,yi,j+1=⋯=yi,d=0x_i = j \iff y_{i,1} = y_{i,2} = \dots = y_{i,j} = 1, \quad y_{i,j+1} = \dots = y_{i,d} = 0$
- 제약 조건:
- $y_{i,j} = 0$이면 $y_{i,j+1}, ..., y_{i,d}$도 0이어야 한다.
- 따라서 모든 $y_{i,j}$에 대해 **$y_{i,j} = 0$이고 $y_{i,j+1} = 1$이면 비용 $\infty$**를 부여한다.
4. 최소 컷 문제로 변환
위 제약을 만족하는 최소 비용을 구하는 문제를 최소 컷 문제로 변환한다.
- $Nd$개의 노드, $N(d-1) + M(2d-1)$개의 간선으로 구성된 그래프에서 최소 컷을 찾는다.
- Dinic 알고리즘 ($O(V^2 E)$)을 사용하여 최소 컷을 구하면,
전체 시간 복잡도는 **$O(N^6 (N+M) \log N)$**이 된다.
5. 이진 탐색을 활용한 최적화
- 위 과정을 이진 탐색을 통해 반복 수행하여 최소한의 간선 변경 횟수를 찾는다.
- 최단 거리를 $d$ 이상으로 만들기 위해 필요한 최소 간선 수정 횟수를 구한 뒤,
그 값이 $K$ 이하이면 가능, 그렇지 않으면 불가능 판별.
최종 시간 복잡도
- 최소 컷 계산: $O(N^4)$ (최악의 경우)
- 이진 탐색을 통한 반복: $O(\log N)$
- 전체 시간 복잡도: $O(N^6 (N+M) \log N)$, 하지만 상수 계수가 작아 실전에서는 충분히 빠름.