배열 $a$에 대해 어떠한 operation을 진행할 수 있고, 이를 1번 진행했을 때 나올 수 있는 $max(a_n - a_1)$을 구하는 문제이다.
operation은 구간 $[l, r]$을 지정한 후에 횟수 $k$를 지정하면 구간에서 왼쪽으로 $k$번 회전하는 연산이다.
처음에는 대충 풀었다.
항상 $a_1$는 배열의 최솟값이 될 수 있고, $a_n$은 배열의 최댓값이 될 수 있다고 하여 제출했지만 틀렸다. ㅎㅎ
다시 지성을 갖추고 접근하여 문제의 핵심을 파악할 수 있었다.
$a_1$과 $a_n$을 포함하지 않고 operation을 진행한다고 하면 의미가 있을까? 즉, $1 < l < r < n$ 인 구간 [l, r]에 대해 operation을 하면 $a_1$과 $a_n$의 값은 영향을 받지 못한다.
이제 $a_1$과 $a_n$의 값이 바뀌는 경우는 어떠한 경우이고, 어떤 값이 될 수 있는지 알아보자.
$a_1$의 값이 바뀌는 경우는 $l=1$인 경우이고, $a_n$의 값이 바뀌는 경우는 $r=n$일 때이다. 즉, 연산의 구간에 해당 인덱스(1 또는 n)가 들어가는 경우이다.
이제 상황을 총 3가지 경우로 나눌 수 있다.
Case1) $l=1$, $r \neq n$ 이 경우에 $r<n$을 의미하므로, $a_n$은 처음과 동일하고, $a_1$은 구간 $[1, n-1]$의 값 중에서 아무 값이나 될 수 있다. 따라서, $a_1$의 best값 $a_{1*}$ = $min(a_{1 \sim (n-1)})$ 이 된다.
Case2) $l \neq 1$, $r=n$ 이 경우에 $1 < l$을 의미하므로, $a_1$은 처음과 동일하고, $a_n$은 구간 $[2, n]$의 값 중에서 아무 값이나 될 수 있다. 따라서, $a_n$의 best값 $a_{n*}$ = $max(a_{2 \sim n})$ 이 된다.
Case3) $l=1$, $r=n$ 이 경우에는 구간이 $[1, n]$이므로, 회전함에 따라 $a_1$과 $a_n$의 값이 같이 바뀌게 된다. 이 경우에 대해 생각해보면, 회전함에 따라 인덱스가 1차이나는 원소끼리 $(a_1, a_n)$ 쌍이 되는 것을 쉽게 알 수 있다. 따라서, 이 경우에는 인덱스가 1차이나는 원소들끼리의 차가 많이 나는 경우 $max(a_{i-1} - a_{i})$가 best가 되게 된다. $i=1$인 경우에 $a_n - a_1$로 처리를 해주는 것을 주의하자!
B. Mainak and Interesting Sequence
배열의 크기 $n$과 배열의 모든 원소의 합 $m$이 주어지면, 문제의 조건을 만족하는 경우가 있는지 여부를 판단해야 하는 문제이다.
또한, 조건을 만족하는 경우가 있다면 그 경우를 출력해야 한다.
이러한 constructive한 문제는 경우를 나누어 생각하는 것이 굉장히 중요하다.
먼저 $n > m$인 경우를 생각해보자.
배열의 크기가 $n$이므로 이 배열의 모든 원소의 합은 적어도 $n$이상이다. 따라서 $n > m$인 경우는 존재할 수 없다. ⇒ NO
이제 $n \leq m$인 경우에 대해서만 생각하면 된다.
먼저, $n = m$인 경우를 생각해보자. 이러한 경우에 모든 원소가 1인 배열을 만들면 성립한다. ⇒ YES
이제 $n < m$인 경우를 생각해보자. 이 경우는 2가지 경우로 나눌 수 있다.
Case1) $n$이 홀수 $n$이 홀수라면, $n-1$개의 원소를 1로 하고 나머지 한 개를 $m-(n-1)$로 하면 된다. ⇒ YES 왜냐하면, $n-1$은 짝수이므로 서로 XOR 연산을 하면 0이 되기 때문이다. 이 경우는 $m$이 홀수든 짝수든 항상 조건을 만족한다.
Case2) $n$이 짝수 $n$이 짝수라면, 위의 Case1) 로직을 적용하면 조건을 만족하지 못한다. 왜냐하면, 여기서는 $n-1$이 홀수이므로 서로 XOR 연산을 하면 0이 되지 않기 때문이다. 따라서, 경우를 더 나눠볼 필요가 있다.
Case2-1) $n$이 짝수, $m$이 짝수 이 경우엔 $n-2$개의 원소를 1로 하고, 나머지 두 원소를 $\frac{(m-(n-2))}{2}$로 하면 된다. ⇒ YES 이렇게 하면 $n-2$는 짝수이므로 XOR연산을 하면 0이 된다.
Case2-2) $n$이 짝수, $m$이 홀수 이 경우엔 불가능하다. ⇒ NO 왜냐하면, $n-2$개의 원소를 1로 한다고 해도, 남은 값 $m-(n-2)$이 홀수이므로 같게 나눌 수 없기 때문이다.
사실, 배열이 조건을 만족하려면 다음과 같은 조건을 만족해야 한다.
배열에서 가장 큰 수를 제외한 모든 수는 짝수개가 돼야 한다!
C. Jatayu's Balanced Bracket Sequence
문제 지문에서는 길이가 $2n$인 문자열을 통해서 $2n$개의 노드를 가진 그래프를 만든다고 하였다.
지문이 뭔 소리인지 몰라서 대충 테스트케이스를 보고 문제에 대해서 파악했다.
길이가 $2n$이고 '('과 ')'로 이루어진 문자열이 주어지며 컴포넌트 개수를 세는 문제이다.
컴포넌트 개수를 세는 것인데, 같은 깊이에서 연결되어 있으면 하나의 컴포넌트로 보는 것 같았다.
즉, '('과 ')' 쌍이 같은 깊이에서 연결되어 있으면 하나의 컴포넌트로 보는 것이다.
말로 설명하기 어려운데 그림을 보면서 이해해보자.
위와 같은 경우는 주황색과 파란색이 각각 하나의 컴포넌트로 답은 2이다.
위와 같은 경우는 주황색, 보라색, 파란색이 각각 하나의 컴포넌트로 답은 3이다.
하나의 컴포넌트라 함은 어떻게 결정된다 하였는가?
바로, 같은 깊이에서 연결되어 있으면 하나의 컴포넌트가 된다.
그렇다면, 하나의 컴포넌트가 확정되는 순간은 언제인가?
바로, 같은 깊이에서의 연결이 끊기는 순간이다! '('와 ')' 쌍이 같은 깊이에서 끊기는 순간에 하나의 컴포넌트가 확정되므로 이때 ans ++ 을 해주면 된다. 즉, 닫힌 괄호 다음에 닫힌 괄호가 나올 때 ans ++ 을 해주면 된다. 참고로, 가장 깊이가 낮은(가장 바깥의) 컴포넌트는 마지막에 따로 세줘야한다.
D. Edge Split
$n$개의 노드와 $m$개로 이루어진 그래프가 있으며, $m$개의 각 간선은 빨간색 또는 파란색으로 칠할 수 있다.
이때 $n$개의 노드와 빨간색 간선으로 이루어진 그래프에서의 컴포넌트 개수를 $c_1$,
$n$개의 노드와 파란색 간선으로 이루어진 그래프에서의 컴포넌트 개수를 $c_2$라고 하며, $max(c_1 + c_2)$를 구하는 문제이다.
실제 대회에서 $c_1 + c_2$의 최댓값이 언제 나오는지를 파악하는 데만 해도 오래 걸렸다.
노드만 있는 그래프에서 간선을 추가함에 따라 컴포넌트가 줄어드는 것은 쉽게 이해할 수 있을 것이다.
간선을 추가해도 컴포넌트의 개수가 줄어들지 않는 경우가 있는가?
위 그래프에서 회색 간선이 추가될 때는 컴포넌트가 1개씩 줄어들지만, 이후에 주황색 간선이 추가돼도 컴포넌트 개수는 그대로이다. 즉, 이미 같은 집합에 포함되어 있는 노드끼리의 간선을 연결시켜도 컴포넌트 개수는 줄어들지 않는다는 것이다. 이에 대한 자세한 내용은 Union-Find 알고리즘을 참고하기 바란다.
따라서, 우리는 $c_1 + c_2$의 최댓값이 언제 나오는지를 알 수 있다.
바로, 각 간선을 파란색 또는 빨간색으로 확정했을 때 현재 $c_1 + c_2$의 값이 1씩 줄어 들어야 한다!
쉽게 말하자면, 각 간선을 빨간색, 파란색으로 칠했을 때 RG와 BG 모두 사이클이 없는 상태를 의미한다.
설명의 편의를 위해서 노드와 빨간색 간선의 집합을 RG라 하고, 노드와 파란색 간선의 집합을 BG라 하겠다.
어떻게 하면 RG와 BG 모두 사이클이 없게끔 간선의 색을 칠할 수 있을까?
$n$개의 노드로 이루어져 있고 $n-1$개의 간선으로 이루어진 그래프를 트리라고 한다. 또한, 이러한 트리는 사이클이 없다는 특징이 있다.
문제에서 간선의 범위는 $n-1 \leq m \leq n+2$이다. 트리는 사이클이 없기 때문에 $n-1$개의 간선을 포함하는 트리를 만들어 RG 또는 BG로 확정할 수 있다. 우리는 RG를 $n-1$개의 간선으로 이루어진 트리로 확정했다고 가정하고 설명하겠다.
RG를 확정했으니 남은 간선들로 이루어진 그래프가 BG가 될 것이다. 간선의 개수에 따라서 상황을 나누어 설명하겠다.
case1) $m = n-1$ 남은 간선은 0개이므로 사이클 또한 없다. 따라서, 이 경우에 RG와 BG 모두 사이클이 없는 상태이므로 정답인 경우에 해당한다.
case2) $m = n$ 남은 간선은 1개이다. 어떠한 간선 1개는 사이클을 만들 수 없으므로 정답인 경우에 해당한다.
case3) $m = n+1$ 남은 간선이 2개인 경우이다. 어떠한 간선 2개로 사이클을 만들 수 없으므로 정답인 경우에 해당한다. 노드 $a$와 $b$를 잇는 간선은 양방향 간선으로 1번만 주어진다고 하였다.
case4) $m = n+2$ 남은 간선이 3개인 경우이다. 이 경우에 간선이 3개이므로 삼각형 모양의 사이클이 만들어질 수 있다. 따라서 BG에 사이클이 존재하는지를 체크하고 존재한다면 BG의 사이클을 제거해줘야 한다.
case4) 에서 BG에 사이클이 존재하는 경우에 어떻게 제거할 것인가?
BG에서 사이클이 존재한다면 BG의 간선 중 하나와 RG의 간선 중 하나를 바꾸면 된다. 하지만, 이 경우에 BG에서 사이클은 사라지지만 RG에서 사이클이 생길 수 있다. 따라서, RG에서 사이클이 안 생기게끔 하며 간선 교환을 수행해야 한다.
이를 수행하는 가장 간단한 방법은 BG의 삼각형 사이클의 세 노드 중에서 가장 깊은 노드 $\alpha$를 다루는 것이다. $\alpha$에서 부모 노드로 가는 RG의 간선과 $\alpha$에서 BG의 가장 얕은 노드로 가는 간선을 교환하면 된다. 이렇게 수행하면 RG는 끊어진 컴포넌트를 다시 연결해주는 상황이기 때문에 사이클이 발생하지 않는다.
느낀점
코드포스는 한 문제라도 잘못 접근하면 시간 소요가 상당히 크기 때문에 핵심 아이디어를 단번에 파악하는 게 관건인 것 같다.
떠올린 문제의 풀이가 심플하지 않다면 그 풀이는 버리고 다시 생각해볼 필요가 있는 것 같다.
