[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번째부터 시작해서 -로 시작하냐 +시작하냐에 따라 달리 뒤집는겁니다. 다시 말해서,

----++---로 최초상태가 있다면

우선 -로 시작하므로 이때는 +가 있기 전의 -까지 뒤집습니다. 당연히 모두 +가 되겠지요.

++++++--- 

+로 시작할때는 다시 -이전까지 이를 모두 뒤집습니다.

---------

이제 다시 -조건에 따라 마지막까지 뒤집으면 해결입니다

모든 상태를 이와같이 접근하면 쉽게 해결 됩니다.