[AC] 1327 소트게임

출처 : https://www.acmicpc.net/problem/1327

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/1327.cpp

난 항상 이런 뒤집는 문제를 좋아하지 않는다. 경험상 뒤집으라는 문제는 생각도 뒤집어야 한다.

나는 이문제에 어떠한 규칙이 있지 않을까 하며 엄청 찾았다. 

몇몇의 규칙을 찾았지만 그 규칙을 전부 적용시키려면 소스가 너무 길어진다.

그러나 늘 말하지만 소스가 길다면 알고리즘은 틀린것이다. 

대게 알고리즘 문제의 정답은 소스가 길지 않다는 점을 알아둬야한다.

그럼 다시 인풋을 보자. 최대가 8이다. 왠지 dfs나 bfs등의 재귀를 사용해도 충분할것 같다.

그리고 8이면.. 12345678인데 거꾸로해도 87654321이다. 약 9천만 정도의 경우의수를 가질 수 있다. 물론 이 전부를 사용하지는 않을 것이다. 아마도.. 그러나 배열의 크기를 얼마를 잡아줘야할지 감이 오지 않으므로 STL의 힘을 빌린다.

그리고 bfs로 구간별로 조금씩 뒤집어본다. 계속 뒤집는다 언젠간 나올것이다. 생각해보면 엄청 뒤집지도 않는다. 왜냐면 불가능한 경우가 엄청 많다. 그리고 중복처리도 걸리게 되니 생각보다 많이 뒤집을수는 없다.

그러나 내풀이의 치명적 결함은 만약 인풋이 1~8까지 가아니라 8개의 숫자이지만 10 20 30 100 이런식으로 2자리의 숫자가 나온다면 풀 수 없다. 그때는 조금 다른 방법으로 접근해야할것이다. 키워드는 튜플이다.

수를 합쳤다가 나눴다가 다시 합쳤다가 나눴다가를 바놉ㄱ하지만 이게 큐를 사용하기에는 깔끔할것이기에 이 문제에는 적합한 방법이라고 볼 수 있다.