BOJ 25384 니은숲 예술가

정해에 소개된 방식과 다른 접근법을 이용한 DP를 사용하면, 정해와 마찬가지로 $O(N^2)$ DP 풀이를 얻을 수 있고, 이것이 UCPC 당시 우리 팀의 풀이였다. 이 글에서는 해당 풀이와, 해당 풀이를 개선해 $O(N)$에 해결하는 법을 소개한다.

1. 방향을 두 조각으로 분리하기

크기 1의 조각부터, 크기 $N$의 조각까지를 순서대로 붙여나가는 것을 생각하자. 새로 붙인 크기 $N$의 조각과 만나는 조각들은 새로 붙인 조각의 방향에 따라 기존 조형물의 윗쪽 또는 아래쪽에 아직 일부분이 남아있는 조각들과, 왼쪽 또는 오른쪽에 일부분이 남아있는 조각들이다.

 

각 조각을 붙인 4가지 방향을, 상하 방향 2가지와, 좌우 방향 2가지 각각의 정보로 분리할 수 있다. 이렇게 분리할 경우 좋은 점은 윗쪽 또는 아래쪽에 일부분이 남아있어 만나는 경우는 오직 상하 방향에, 왼쪽 또는 오른쪽에 일부분이 남아있어 만나는 경우는 오직 좌우 방향에만 영향을 받는다는 점이다. 정확한 분석은 2문단에서 설명한다.

 

이 사실을 알았다면, 문제를 상하 방향과 좌우 방향에 대해 독립적으로 해결할 수 있다. 답은 가능한 상하 방향 배열의 개수와 좌우 방향 배열의 개수의 곱이 된다. 그런데, 두 문제는 방향만 다를 뿐 완전히 동일한 문제이기에, 좌우 방향 문제만 해결한 후, 좌우 방향 배열의 개수의 제곱이 답이 된다.

2. $O(N^2)$ DP

우선, 좌우 방향으로 만나는 조각들에 대한 정확한 분석이 필요하다. 일반성을 잃지 않고 $N$번 조각을 오른쪽에 붙였다고 하자. 또한, $j$번 조각과 $i$번 조각이 서로 다른 방향으로 붙여진 최소 $j$를 $L_i$로 정의하자. $L_N+2 \le i \le N$인 $i$에 대해, $i$번 조각은 바로 왼쪽의 $i-1$번 조각과만 좌우 방향으로 만난다. 하지만, $L_N + 1$번 조각은 여러 조각들과 좌우 방향으로 만날 수 있는데, 해당 조각들은 $L_N + 1$번 조각 이전에 마지막으로 오른쪽 방향으로 조각을 붙인 후, 왼쪽 방향으로 조각들을 붙이면서 오른쪽에 하나씩 자리를 차지하게 되는 조각들이다. 즉, $L_{L_N}$번 조각부터 $L_N$번 조각까지가 $L_N + 1$번 조각과 만나게 된다.

 

해당 사실을 이용한 점화식을 설계하자. $D_{i, j}$를 $i$번 조각까지 붙였을 때, $L_i = j$인 경우의 수로 정의하자. $i - 1$번 조각과 $i$번 조각의 방향이 같다면 $L_i = L_{i-1}$이고, 그렇지 않다면 $L_i = i - 1$이다. 이를 이용해, DP 전이를 두 가지로 나눌 수 있다. 단, 1 이상 $N - 1$ 이하의 모든 $i$에 대해 $C_i \neq C_{i+1}$을 가정한다.

 

$i - 1$번 조각과 $i$번 조각의 방향이 같은 경우, $i$번 조각은 $i - 1$번 조각과만 만난다. $C_i \neq C_{i-1}$이므로, 전이는 $1 \le j < i - 1$인 모든 $j$에 대해 $D_{i-1, j} \rightarrow D_{i, j}$이다.

 

$i - 1$번 조각과 $i$번 조각의 방향이 다른 경우, $i$번 조각은 $L_{i-1}$번 조각부터 $i-1$번 조각까지와 만난다. 전이는 $j$번 조각부터 $i -1$번 조각 사이에 $i$번 조각과 $C$값이 같은 조각이 없는 모든 $j$에 대해 $D_{i-1, j} \rightarrow D_{i, i-1}$이다. $S_i$를 $j$번 조각부터 $i-1$번 조각 사이에 $i$번 조각과 $C$값이 같은 조각이 없는 최소 $j$라 하면, $\sum_{j=S_i}^{i-1} D_{i-1, j} \rightarrow D_{i, i-1}$로도 표현할 수 있다.

 

1번 조각의 경우 방향을 정의하기도 애매하고 여러모로 초기값이 문제가 되는데, 회전을 같은 경우로 처리하지 않는다는 점을 이용해, 1번 조각과 2번 조각의 서로 방향이 다르다고 설정해주자. $D_{2, 1} = 1$로 설정하고, 3 이상의 $i$에 대해서 직접 점화식을 계산하면 된다.

3. $O(N \log N)$으로 개선하기

대부분의 $D_{i,j}$는 $D_{i-1,j}$와 같고, 다른 것은 오직 $D_{i, i-1}$이다. 또한, $D_{i, i-1}$은 $D_{i-1}$ 배열 상의 구간 합을 이용해 구할 수 있다. 즉, 현재의 $D$배열을 세그먼트 트리 또는 펜윅 트리를 이용해 관리한다 생각할 수 있다.

 

업데이트는 결과적으로는 굉장히 간단하다: $\sum_{j=S_i}^{i-1} D_j$을 세그먼트 트리 쿼리를 이용해 $O(\log N)$에 구한 후, $D_{i-1}$에 해당 값을 더해주면 된다.

 

답은 모든 업데이트 이후 $\sum_{j=1}^{N-1} D_j$이다.

 

코드: http://boj.kr/787245c89843420ab5762b8b48fc7a67

4. $O(N)$으로 개선하기

세그먼트 트리 없이 부분합을 이용하는 것이 가능함을 어렵지 않게 관찰할 수 있다.

 

코드: http://boj.kr/e2ed901f35844076840f6db6221f66bc