1204D2 - Kirk and a Binary String (hard version)

D번치고 아주 까다로운 문제였다. 열심히 고민하다 결국 못 풀었다.

편의를 위해 다음 조건을 만족하는 두 binary string을 s와 t를 $s \approx t$로 표기하자.

1) s와 t의 길이는 서로 같다.

2) s와 t의 같은 위치에 있는 substring은 maximum non-decreasing subsequence의 길이가 같아야 한다.

s가 주어질 때, $s \approx t$이며 0의 개수가 최대한 많은 t를 만드는 문제이다.

풀이는 굉장히 쉬운데, s에 "10"이 있으면 그 위치는 t에도 동일하게 "10"으로 놔두고, s에서 "10"을 제거한 뒤 같은 과정을 반복하면 된다. 더 이상 s에 "10"이 없다면 나머지는 다 0으로 채워도 무방하다.

왜 이런 풀이가 성립하는지 증명해보자.

1) s = "10"이면 $s \approx t$를 만족하는 t는 "10"밖에 없다.

4가지 경우 다 해보면 된다.

2) 두 문자열 s, t의 임의의 같은 위치에 "10"을 추가한 두 문자열을 s', t'라 할 때, $s \approx t$와 $s' \approx t'$는 동치이다.

nond(s) = 문자열 s의 maximum non-decreasing subsequence의 길이라 하자.

임의의 문자열 s에 대해,

nond(s + "1") = nond(s) + 1

nond("0" + s) = nond(s) + 1는 자명하게 성립한다.

또, 임의의 문자열 s1, s2에 대해

nond(s1 + "10" + s2) = nond(s1 + s2) + 1 또한 성립한다. 왜냐하면 s1 + "10" + s2의 최대 감소하지 않는 부분 수열에는 s1 + s2의 최대 감소하지 않는 부분 수열에 0, 1 중 정확히 하나만이 더 추가되기 때문이다.

위 3가지 식에 의해 2)도 성립함을 알 수 있다.

이제 문제를 풀어보자. 주어진 문자열 s에서 "10"을 제거해 나가는 방식으로 새로운 문자열 t를 만들자.

t는 00...0011..11꼴일 수밖에 없다. 이제 0으로만 이루어진, t와 길이가 같은 문자열 u가 있다고 할 때 $t \approx u$가 성립한다.

s는 t의 특정 위치에 "10"을 추가하는 방식으로 문자열이므로, u에 방금과 같은 위치에 "10"을 덧붙이는 방식으로 만든 문자열 v는 $s \approx v$가 성립하며 0이 이보다 많아질 수 없다.