== UCPC F. parentheses recover 풀이 == (feat. 모델링의 중요성)

0. 문제를 풀 때는 다른 문제로 바꿔서 푸는 경우가 많이 있습니다. 미로 최단거리를 그래프로 바꿔서 bfs로 푸는 것이 그 예시입니다. 하지만 문제를 바꿔서 풀 때는 조심해야 합니다. 문제를 바꾸는 과정에서 정보 손실이 일어날 수 있고, 일부 만족해야 하는 성질이 사라져 못푸는 문제가 되어버릴 수 있습니다.

 UCPC F 문제로 나온 parentheses recover의 풀이를 설명하면서, N^3 풀이와 N^2 풀이의 모델링에 나타나는 차이를 설명해 볼 것입니다.

(스포 방지선)

---

1. 가능-불가능 여부 확인

 문제를 풀기 위해서는 먼저 괄호 문자열 S, T가 주어졌을 때 조건을 만족하는지 알 수 있어야 합니다. (그리고 일반적으로 풀이를 이런 단순한 문제에서 시작하는 것은 매우 좋은 습관입니다.) 이 문제는 N^2 DP를 쓰면 쉽게 가능합니다.

 문제를 풀기 전에 괄호문자열이 올바른지 확인하는 것부터 잠깐 짚고 넘어가면,

 1) '('를 1, ')'를 -1로 했을 때, 모든 누적합이 음이 아닌 정수

 2) '(' 개수 = ')' 개수

를 만족하는 것과 괄호문자열이 올바른 것이 필요충분입니다.

 

 (()())()는 누적합이 순서대로 0, 1, 2, 1, 2, 1, 0, 1, 0으로 위의 조건을 모두 만족하고,

 ())(()는 0, 1, 0, -1, 0, 1, 0으로 음수가 있어 1번 조건을 만족하지 않고,

 (()는 '(' 2개, ')' 1개로 2번 조건을 만족하지 않습니다. (보통 2번 조건은 누적합 끝이 0인지로 확인하는 것이 더 편합니다)

  S = ))(()(())((, T = (((())))()) 라고 하고 간단하게 시각화해서 보여드리면, 

DP 테이블

 칸에서 아래로 움직이는 것은 S에서 글자 하나를 가져오는 것, 오른쪽으로 움직이는 것은 T에서 글자 하나를 가져오는 것을 의미합니다. 이런식으로 격자로 모델링하면, S와 T를 순서를 유지하며 합치는 것을 격자에서 아래와 오른쪽으로만 이동하는 경로를 찾는 문제로 바꿀 수 있습니다.

 각 칸에 써진 숫자는 그 칸에 도착했을 때 괄호문자열의 누적합을 적은 것으로, (칸의 왼쪽에 있는 괄호의 합) + (칸의 위쪽에 있는 괄호의 합)을 계산한 것입니다. 옳은 괄호문자열의 1번 조건을 만족하기 위해서는 지금까지 나온 누적합이 0보다 크거나 같아야 하므로, 옳은 괄호열을 만드는 경로는 0보다 작은 칸(연파랑)을 지나지 않아야 합니다. 2번 조건을 만족하기 위해서는 가장 오른쪽 아래가 0이어야 합니다.

 경로와 괄호문자열을 합치는 것은 일대일 대응 관계이기 때문에, 경로가 존재하면 S, T가 문제의 조건을 만족하는 것이고, 아니면 아닌겁니다. 위에서는 경로가 있기 때문에 조건을 만족하고, 실제로 빨간 경로를 확인해보면 옳은 괄호문자열이 나오는 것을 알 수 있습니다.

※ 합친 괄호문자열: ( ((())) (()) )  (()) () () ()

 위의 방법대로 하면 S, T가 조건을 만족하는지 확인할 수 있습니다. 그리고 이 성질로 문제를 푸는 것은 매우 괜찮은 선택지처럼 보입니다. 격자 위에서 경로가 존재하도록 하는 괄호열 S의 개수를 세면 될 것 같습니다. 물론 그냥은 안되고(...) 몇 가지 성질을 찾아서 잘 볶으면 N^3이 된다고 합니다.

 하지만 제가 문제를 풀 때 이 모델링은 많은 것을 놓치고 있다고 생각했습니다. 격자칸의 숫자를 0 이상과 미만으로 단일화시켰고, 붙어있는 칸은 값이 1 차이나는 것과, 인접한 열은 차이가 모두 동일하다는 것이 모두 사라져 있었습니다. 이 성질들은 꽤나 유용해보였기 때문에, 새로운 모델을 만들어 문제를 풀어보기로 했습니다.

2. 다른 방법

 위와 같이 S = ))(()(())((, T = (((())))()) 라고 합시다. 먼저 아래처럼 S로 지형?을 만듭니다. 지형은, 가로는 괄호열 길이, 세로는 누적합을 나타냅니다. 바다 높이는 처음에는 0에 위치해 있고, 이것을 바꿔나갈 것입니다.

 

그리고 토끼 무리가 이 지형에서 살고 있다고 가정하는데, 토끼 무리는 다음과 같이 움직입니다.

 0) 토끼는 왼쪽으로 갈 수 없다. (오른쪽으로만 이동한다)

 1) 토끼는 오른쪽으로 이동할 수도, 가만히 있을 수도 있다.

그 이외에도, 

 2) 토끼는 (당연하게도) 바다에서 살 수 없다.

 3) 시간 0에 토끼 무리는 가장 왼쪽 끝에 살고 있으며, 토끼는 매우 빠르다.

를 가정합시다.

 이제 바다 높이를 시간에 따라 바꾸려 하는데, 만약 시간 t초에 T의 t번째 글자가 '('라면 높이를 1 낮추고, ')'라면 1만큼 높이는 것으로 생각해봅시다. 그러면 대충 다음과 같이 될 것입니다. (T = "(((())))())")

 

 시간에 따른 바다 높이 변화

 토끼는 시간 0에는 가장 왼쪽만, 시간 1에는 x=1 지점까지만 갈 수 있지만, 시간 2에 섬의 모든 곳으로 퍼지게 됩니다. 마지막으로 시간 11에서는 x=7, 11에만 남아있게 되겠네요.

 이런식으로 모델링을 하면, 조건을 만족하는지는 다음과 같은 방법으로 알 수 있습니다.

 1) 토끼가 가장 오른쪽 끝에 도달하여 끝까지 살아남을 것 (by. 괄호열 1번 조건)

 2) 마지막 시점에 바다 높이와 오른쪽 끝 지면 높이가 일치할 것 (by. 괄호열 2번 조건)

 토끼의 움직임이 위에서 본, 격자에서 오른쪽이나 아래로만 움직이는 것과 완벽하게 동일한 효과를 내게 됩니다. 오른쪽으로 움직이는 것은 토끼 움직임의 조건이고, 아래로 움직이는 것은 토끼가 시간역행을 하지 않기 때문에 가능한 것입니다. 때문에 끝에 도달한 토끼의 움직임을 확인하여 가만히 있다면 T를, 오른쪽으로 움직였다면 S를 추가하는 식으로 올바른 괄호열을 만들 수 있습니다. 그리고 올바른 괄호열을 토끼 움직임으로 똑같이 만들 수 있으니까, 일대일 대응 관계가 됩니다.

 2번 조건이 약간 거슬리기 때문에 모델을 약간 바꿔봅시다. 지형 오른쪽 끝에 내리막을 잔뜩 만들면 조건 하나로 끝낼 수 있습니다.

 1) 가장 오른쪽 토끼가 x=|S| 지점에 있을 것

3. 진짜 문제 풀기

 위에서 가장 오른쪽 토끼의 위치만이 중요하다는 것을 알았습니다. 그러면 DP테이블에 (현재 시간, 가장 오른쪽 토끼)를 넣고 돌리면 되겠네요. 풀이 PPT에 있는 이상한 정의는 풀어쓰다보니 그렇게 된 것이고, 사실 가장 오른쪽 토끼의 위치를 의미합니다.

 점화식도 약간의 고찰을 하면 만들 수 있습니다. 시간 t에 가장 오른쪽 토끼 A의 위치가 x일 때,

 1) 해수면이 높아진 경우.

-x 오른쪽은 토끼가 살 수 없습니다.

-시간 t+1에 x의 왼쪽 지형 중 바다 위에 있는 가장 오른쪽 위치(prv[x])에는 토끼가 살고 있습니다.

증명) x의 왼쪽이 내리막인 경우. prv[x] = x-1이고, x-1에서 x로 움직이지 않은 토끼는 살아있습니다.

x의 왼쪽이 오르막인 경우. t에 토끼 A가 있으려면 prv[x]를 한 번이라도 지나야 하는데, 그 순간부터 시간 t까지는 바다의 높이가 x의 고도를 넘을 수 없습니다. 즉, prv[x]에서 오른쪽으로 가지 않은 토끼는 살아있습니다.

2) 해수면이 낮아진 경우

-시간 t+1에 가장 오른쪽 토끼의 위치는 토끼 A가 오른쪽으로 최대한 이동한 곳이 됩니다.

PPT에 있는 말도 안되게 이상한 DP 정의와 점화식은, 사실 이런 이유에서 나온 것입니다.

매우 대충 써져있는 풀이 슬라이드의 모습

 위에 나온 모든 값은 전처리로 N^2에 계산할 수 있고, 점화식도 항이 2개뿐이라서 N^2에 됩니다.

4. 후기

 드디어 이 문제 풀이를 마음에 들 만큼 설명해서 행복하네요. 대회때는 모델링이 어렵지만 성공하면 점화식도 꽤 빨리 나오고(고인물 기준) 코드도 짧아서 일부는 풀 수 있을 줄 알았지만, 매우 뜬금없는 모델링이어서 그랬는지 러시아쪽 대회에서도 0솔을 띄우는 업적을 남겼습니다. (제가 기여한 문제가 Prime New Year Contest에 나올 수 있는 영광(?)을 얻게 되었습니다)

 모델링 과정에서 얼마나 많은 정보가 사라지는지 알려면 수많은 시도와 실패와 성공을 경험해봐야 하는 것 같습니다. 문제수도 많고, 모델링도 많은데다가, 그때마다 사라지는 정보가 다르다보니 말로 전달할 수 있는 내용이 아닌 것 같습니다. 이 문제같은 경우는 "풀이에 도움이 될 것 같은 성질들"이 사라지는 것으로 대충 추측했지만, 문제중에는 정보를 없애고 단순화시키면서 푸는 경우도 많습니다.

끝!