[platinum1] [해설안봄, 분류안봄]1078 뒤집음

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

 

 

 

요새는 그 쉽다는 싸피 코테에서 입출력 문제로 0 문제를 푼 굴욕적인 사건이후,  플레 이상의 문제를 끙끙대며 푸는거에 회의감을 느끼고 있다. 고난도 문제를 오랜시간 들여 풀어봤자 실전에서는 솔직히 도움이 거의 안되기 때문이다.. 사실 지금까지 알면서  문제 해결력과 정신적 체력(?)을 늘린다는 명분하에 골드 이하 문제들을 외면해 왔지만.. 이제는 더 이상 그럴때가 아니다.  이러다간 영영 취업 못할 수도 있겠다는 불안감이 든다.  

 요 근 래 일주일은 실전 연습을 위해 골드5~골드4 문제를 주구장창 돌리고 있고,. 고난도 문제는 이제 가끔씩 풀려고 한다. 1078 뒤집음 문제도 사실 일주일 전에 풀었는데 글쓰는게 너무 귀찮아서 방치하고 있었다.,..  

 

이 문제는 사실 아이디어는 그렇게  어렵진 않은데 조건 분기가 너무 많고 예외 케이스로 죽어나가는 문제였다.

 

 숫자  857232를 예로 들어보자.  맨뒤 숫자 2부터 생각해보자,

숫자를 뒤집어 빼면  맨앞 숫자와 맨뒤 숫자를 서로 뒤집어 빼는 꼴이 될 것이다. 그렇다면 다음과 같은 두가지 경우가 있다.

 

1. 첫번째 :   맨뒤자리 - 맨앞자리 = 2

 

 

다음과 같은 경우가 있을 것이다. (앞자리는 생각않는다) .  x의 맨뒤자리 - 맨앞자리 == 2 일때     x - x뒤집음 에서의 맨뒷자리는 2가 될 것이다.

 

2. 두번째 : 맨앞자리 - 맨뒷자리 = 10 - 2

 이번 경우도 x - x 뒤집음 = 2가 된다. 

 

즉 뒷자리가 a라면

뒷자리 - 앞자리 ==a    or  앞자리 - 뒷자리 = 10 - a  인 경우 2가지가 있을 것이다.

 

맨뒤자리 - 맨앞자리 == 2 일때 

(맨앞,맨뒤) = (0,2) or (1,3) or(2,4)....  (7,9)  의 경우가 있다. 

그러나 최솟값을 찾아야 하므로 그리디 하게 (0,2)인 경우만 따지면 된다.

 

마찬가지로 맨앞자리 - 맨뒤자리 == 8  일때도 (8,0), (9,1)인 경우가 있겠지만 (8,0) 인 경우만 생각하면 된다.

 

 

 

이번엔 10의 자리도 생각해보자.

 

 

 

이번에도 마찬가지로 앞자리 - 뒷자리 == 3   해서 (0,3)을 도입하면 될것인가? 

이번에는 다르다. 왜냐하면, 위의 경우  맨뒷자리에서  0 - 8 을 하는과정에서 10의자리 수를 하나 갖다가 썼기 때문이다. 

따라서 이번에는 앞자리 - 뒷자리 == 3 + 1 = 4 가 되어야 한다.  (40 - 8 = 32)이므로

 

 

 

그래서 다음과 같이 두가지 경우가 있다.

 

1. 10 ^ 1 자리 - 10 ^ 4 자리 == 4

 

 

 

2. 10^4자리 - 10 ^ 1 자리 == 10 - 4 = 6

이렇게 된다.

 

 

종합해 보면, 

10 ^ n 자리를 고려한다고 할 "때   10  ^ n - 1 자리에서   (a, 0) 꼴로 썼으면  n자리에서 1을 하나 갖다쓴 꼴이되므로.,  

  D(==857232)에서의 n 자리 수를 b라고 할 때      앞자리 - 뒷자리 = 10 - (b + 1 )  or  뒷자리 - 앞자리 = b로 생각하면 된다.

 

 

이렇게 하면 D는 100만까지이므로   뒷자리를 하나씩 채울때마다 앞자리들과 숫자를 합쳤을 때 (위의 경우 앞자리 86 + 뒷자리 00 = 8600 )  여기서 뒤집은 수를 빼보았을 때 D인지 (8600 - 0086 == D?) 따져보므로써 답을 구할 수 있다. 100만까지이므로 7자리이므로 2^7 의 경우의 수이다.

 

이렇게 생각하면 꽤나 간단하지만, 나는 풀때 무지성  2^n 으로 풀자니 앞자리도 충분히 필터링 해서 더 최적화를 시켰다.

그러나 땅을 치고 후회하는게 앞자리까지 고려하려면 수많은 반례 지뢰들이 기다리고 있어서... 진작 2^n 브루트포스로 끝낼 걸 하고 후회가 되었다.

 

우선 앞자리를 고려할 때 가장 기초적인 생각은 

 

 

다음과 같은 상황에서  앞자리 부분, 80 - 04 == 76 이 되므로 85가 되지 않는 다는 것이다.

따라서 86 - 00 인 경우만 가능하다.    86인 경우는 뒤가 (0, a)인 경우일ㅇ때  한자리를 빌려줘서 85가 될 수 있다.

 

 이런 경우 앞자리는 85가 될것이다.

따라서 x - x뒤집음 에서 앞자리 (86- 00 == 86)  와 D에서의 앞자리(85)의 차이가 1미만인 경우 가능하다.

 

이 경우를 필터링 해주면 대부분의 경우 O(n)의 경우로 금방 끝날 것이다.
D의 길이가 l일 때 10^(l - 1 - n) 과 10^(n)자리를 고려할 때 point를 두어서 어디까지 뺐는지를 저장해야 한다. ( 86 , 00 )의 경우 point : 2 까지.   (860, 300)의 경우 point : 3까지

 

그러나 point를 따지는 과정에서 많은 반례들이 존재한다.

 

다음의 경우 point가 1일때  1 - 0 = 0 으로 D의 9 와 매칭이 안되는 경우가 있다.

이 경우 point에서 D가 9, x 가 1일때는  x의 point는 하나 더 증가시키고, D의 포인트는 홀딩해서  (10 - 01) == 9 가 될 수 있도록 예외처리 해야한다.

 

 

 

또한 뒷자리가 0으로 끝날 때는 맨앞자리 - 맨뒷자리 == 0 이되어야 한다. 

맨뒷자리의 경우 가  0이면 맨앞자리도 0이되어야 하는데, 맨앞자리는 0이될 수 가 없으므로  그리디하게 0바로 다음의 수 (1,1)로 결정해야 한다.

 

위와 같은경우  그렇다. 

 

 

 

눈물의 뻘짓 쇼를 증명하기 위해 작성한 코드를 첨부한다.