[platinum2][해설안봄,분류안봄] 1467 수 지우기

https://www.acmicpc.net/problem/1467

 

 

싸피 시험 후 계속 골드 문제로 양치기 중이라 오랜만에 고난도 문제를 포스팅 하게되었다.

이 문제는 다른 수학 문제들 처럼 외유내강형 문제로, 쉬운줄 알고 섣불리 들어갔다가 두들겨 맞은 문제다.

 

처음 생각한 아이디어는 그리디하게 앞에서 부터  n+1 번째 수 > n번째 수 이면 n 번째를 지우면 될거라고 생각하였다.

이런식으로 말이다. 얼핏보면 문제가 없어보이지만 여기에는 반례가 존재한다.

 

 

다음을 살펴보자. 아까 풀었던 방식대로 그리디하게 앞부터 3을 지우게 되면 

5 2 5 5 3 이 된다.

3을 지우고 뒤에 숫자를 앞으로 오게 해 더 큰 수를 만든다는 로직이었다.

 

그런데 이 경우에는  5를 3개를 지워야 하는데 그럼 모든 5가 지워지게 된다.

이런 상태에서 첫번째 3을 지우게 되면, 첫번째 숫자는 2가 되므로 수가 작아진다. 최종적으론 23 이 된다.

 

따라서 뒤의 3을 지워야 한다. 그럼 32가 된다.

 

이문제를 해결하기 위해 처음 든 생각은 그럼   n번째일 때  수가 k이면 n~마지막 까지 k의 갯수를 미리 구해놓은 뒤 

남은 지워야할 k의 갯수 == n~마지막까지 k의 갯수 라면  이때 미리 k를 다 지워버린 다는 것이었다. 아래와 같은 방식으로 

 

결국 첫번째 수  > 두번째 수 이므로 첫번째 3은 지우지 않게 된다.

 

 

그런데 이 방법도 반례가 있다.

 

우선 위의 경우를 지금까지 생각한 아이디어로 해보자.

n = 1, 2, 3 일때 n+ 1번째 수보다 작으므로 앞의 숫자 세개는 안지운다. 그러다 다음 3은 뒤의 3의 갯수가 지울 3의 갯수와 같으므로 모두 지운다.

그다음 수 4는 뒤의 수가 5이므로 지운다.

다음과 같이 되고,  뒤의 까지 5의 갯수 == 지워야 할 5의 갯수 == 3이므로 뒤의 수를 모두 지운다.

그러나 지우고 보니 1,2,3번째 5의 뒤에는 7이 오게 되고, 사실 그러면 먼저 1,2,3 번째 수를 지워야했다..

 

다시 말해 뒤의 남은 숫자 갯수 == 지울 개수라고 해서 뒤의 숫자를 먼저 지우는 것은 옳지 않다. 뒤의 숫자를  미리미리 지웠지만, 지우다보면 결국 앞의 숫자를 지우는 것이 최선일 경우가 생기기 때문이다.

 

이러한 경우를 해결하기 위해서 다음 아이디어는 이렇다.

 방금처럼 뒤의 숫자들을 미리미리 지워봤자 앞의 숫자를 지워야 할 상황이 올 수도 있으므로, 앞의 숫자들부터 이 숫자를 지워야 할지 말아야 할지 딱 단정을 짓는 것이다.

첫번째 수에서 첫번째 수를 지워야 할 경우는 오른쪽을 탐색했을때 5보다 큰 7 이 첫번째 수 옆에 붙을 수 있을 경우이다.

3 두개, 4 한개, 5 3개를 지워야 하는데,   지울 수에 모두 포함이 되어있다. 따라서 2~7번째 수를 미리 지울 수 있다.

 

그런데 이제 5는 더이상 지울수에 없으므로 첫번째 수는 결국 지우지 않게 된다.

만약 지울 수에 5가 한개 더있었으면 첫번째 수도 지우게 될 것이다.

 

그런데 눈썰미가 빠르다면 여기에 문제가 있다는 것을 알 수 있다/

다음과 같이 5 옆에 7이 붙게 하여도, 지울 7의 갯수 = 남은 7의 갯수라면 7은 없어지게 되고,   7 다음의 4는 5보다 작게 되어 앞의 수 5 5 3 4 5 3 을 지우는 의미가 없게 된다. 

 따라서  첫번째 수 옆에 8번째 수를 두는 것을 목표로하고 2~7번째 수를 지우기로 할 때, 8번째 수가 살아남을 수 있는지 아까와 같은 방식으로 미리 체크할 필요가 있다.

 

 

그런데 이미 두들겨 맞을만큼 맞았다면, 여기에도 의구심이 들 수 있다.  아까처럼 7을 미리 뒤에서 부터 지우는데,  혹시 7을 앞에서 부터 지워야 할 상황이  있을 수도 있지 않을까?

이를테면 다음과 같은 상황 말이다

다음과 같은 상황에서는 7옆에 8이 붙을 수 있으므로 , 앞에서부터 7을 지워야 할 것이다.

다음과 같이 말이다.

 

그러나 이경우는 고민하지 않아도 된다. 왜나하면 이미 2번째 7에서 다음 수로 8을 붙히기 위해 2~12번째 수를 모두 다 지워버렸기 때문이다.

 

 즉 고민하던건 7을 뒤부터 지우려할때  혹시라도 앞에서부터 지워야 할 상황이 오지 않을 까 걱정 한 것이다. 그러나 앞에서부터 지워야 할 상황은 7 보다 큰수 8 을 7옆에 붙힐 수 있을 때 발생하는 것이고,  이 경우는 이미 2번째에서 처리가 되었다.

 

 

이렇게 수많은 반례를 해쳐나가며 답을 구해보았다. 

정말 쉽지 않은 문제였다. 

이런 문제는 그냥 챌린지 정신으로만 당분간 가끔씩 풀고 , 계속 양치기로 가야겠다..