[platinum5] [해설, 분류안봄] 31421 호떡 뒤집기

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

 

적당한 난이도의 애드훅 문제였다.

앞면을 0, 뒷면을 1이라한다.

000000000..00 부터 시작하고, 목표배열에서 앞뒤가 바뀌는 부분쪽을 뒤집어 준다는 아이디어는 어렵지 않다. 0일때 뒤집는 것이므로 인덱스 1~ n까지 뒤집는 것이다.

 

 

 

목표배열이 

110011100 일때 다음의 순서대로 뒤집을 수 있다. (2, 4 , 7 번째 뒤집기)

 

그런데 이러한 경우는 배열의 끝이 0일때만 가능하다.  N - 1번째 , N번째 목표배열 모두 0일때 1 ~ N - 1 번째를 뒤집는 것이 마지막이고, 뒤집었을 때 N - 1번째는 1 ,  N번째는 0 으로  N번째 가 1이 될 수는 없기 때문이다.

이점을 해결하기 위해선 지금까지는  x , x + 1번째 모두 0일때만 골라서 뒤집었고,  x, x + 1번째 모두 1일때도 뒤집어야 한다.

 

 

목표숫자가 110011111 , 즉 맨뒤가 1일때    다음과 같이 뒤집을 수 있다.

 

 

 

 

 

x번 째, x+1번째 숫자가 다를때의 x배열을 x1,x2,x3.... 이라하면

맨뒤자리가 0이면 ->  x1,x2,x3,x4... 순서대로 뒤집기

맨뒷자리가 1이면 -> X1,X2,X3...X N,X N-1 순으로 뒤집기 (1을 뒤집는 경우엔 x+1 ~ N까지 뒤집으므로)

 

반드시 예외가 있을것 같지 않은가.

예외는 목표 배열의 모든 수가 1(뒷면)일때,   x배열크기가 1인데 맨뒤가 1인 경우가 있다.  이 경우는 목표배열로 만들 수 없다.

또 한개 예외는 모든 수가 0(앞면)일때  0번뒤집기 이다.