[백준 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)