[Code Jam] 2016 Qualification Round B.Revenge of the Pancakes
이어서 올리는 코드잼 기출문제 입니다.
역시 해석하는데 시간 좀 걸렸습니다.
해석하고 나면 별게 아닌데 영어가 허접하니 뭐 놓치는게 없나
꼼꼼이 읽다보면 시간을 많이 필요로 하네요..
여하튼 문제에 따라 주어진 팬케이크들의 상태를 모두 happy-side로 바꾸는겁니다
즉 +로 말입니다. ----++가 있으면 ++++++ 이렇게요
문제의 조건에 따르면 한번 팬케이크를 뒤집을 땐
순서가 뒤 바뀝니다. 다음과 같이 말이죠
if we number the pancakes 1, 2, ..., N from top to bottom, you choose the top ipancakes to flip. Then, after the flip, the stack is i, i-1, ..., 2, 1, i+1, i+2, ..., N. Pancakes 1, 2, ..., i
그러니까
++--++가 있는데 3번째까지 뒤집겠다 하면
+--가 되는겁니다. 순서와 면 모두 뒤집히는 겁니다.
이러한 조건에 따라 문제를 풀면 되겠습니다
처음에는 너무 어렵게 문제를 접근했습니다.
동적계획법이겠거니 하면서 재귀적으로 문제를 풀어 나가려 했습니다.
기저조건은 당연히 모두 ++++일때 이겟죠.
문자열 길이도 large data-set에서 100이면 할만하다 생각했지만
막상 시작하니 이를 문제 조건에 맞게 풀어 나가기가 너무 어려웠습니다.
그리고 아예 처음부터 다시 시작해서 접근하니 드디어 해결이 됐습니다...
다른건 아니고 0번째부터 시작해서 -로 시작하냐 +시작하냐에 따라 달리 뒤집는겁니다. 다시 말해서,
----++---로 최초상태가 있다면
우선 -로 시작하므로 이때는 +가 있기 전의 -까지 뒤집습니다. 당연히 모두 +가 되겠지요.
++++++---
+로 시작할때는 다시 -이전까지 이를 모두 뒤집습니다.
---------
이제 다시 -조건에 따라 마지막까지 뒤집으면 해결입니다
모든 상태를 이와같이 접근하면 쉽게 해결 됩니다.