[백준 1784] 팰린드롬 인코딩

티어: 골1

트릭을 알고 무릎을 탁 쳤던 허망한 애드 혹 문제였다.

아이디어의 핵심은 문자열에서 처음 발견되는 011 또는 100 뒤에 오는 모든 문자는 삭제 가능하다는 것이다. 왜 그럴까?

0과 1은 서로 바뀌어도 일반성을 잃지 않으니 100인 경우만 증명해보이겠다.

$a$, $b$는 1 또는 0으로만 이루어진 길이 0 이상의 문자열이다.

$s$는 1로만 이루어진 길이 0 이상의 문자열이다.

0. $a + 100 + b$#

1. $a + 1000 + b$#

00을 0으로 바꿔서 처음 형태인 $a + 100 + b$로 만들 수 있다.

2-1. $a + 10010 + b$#

1001을 10으로 바꿔서 처음 형태인 $a + 100 + b$로 만들 수 있다.

2-2-1. $a + 10011 + s$#

11을 1로 바꾸는 과정을 반복해 $a + 1001$ 형태를 만들고 1001을 10으로 바꿔서 $a + 10$ 형태로 만들 수 있다.

2-2-2. $a + 10011 + s + 0 + b$#

11을 1로 바꾸는 과정을 반복해 $a + 10010 + b$ 형태로 만들 수 있다. 이후 1001을 10으로 바꿔서 처음 형태인 $a + 100 + b$로 만들 수 있다.

결론#

결론적으로 $b$의 길이가 0이 되기 전까지 위 과정을 계속 반복하면 $a + 100$ 또는 $a + 10$ 형태에 도달하게 된다. $a + 100$인 경우 00을 0으로 바꿔서 $a + 10$ 형태로 만들 수 있기 때문에, $a$에 관계없이 100 뒤에 오는 모든 문자는 삭제 가능하다.

이후 $a$에 있는 연속된 1과 0들을 모두 1과 0으로 바꿔준다면 가장 짧은 길이를 가지게 된다. (문자열에서 처음 발견되는 100을 기준으로 잡았기 때문에, $a$를 팰린드롬 인코딩하면 그 결과는 항상 1과 0이 번갈아 배치된 형태이다. 따라서 짝수 길이인 팰린드롬 문자열을 더 이상 찾을 수 없음이 증명된다.)

var input = require('fs').readFileSync(0,'utf8').trim()
if(input.search(/100|011/) != -1) {
    input = input.slice(0,input.search(/011|100/)+2)
    
}
console.log(input.replace(/0+|1+/g, m => m[0]).length)