BOJ 1146 지그재그 서기

서로 키가 다른 사람 n명이 주어질 때, 문제에 주어진 규칙에 따라 줄을 서게 되면 키가 큰 사람 뒤엔 작은 사람이 작은 사람 뒤엔 큰 사람이 서게 되어 지그 재그 모양으로 서게 된다.
이렇게 설 수 있는 경우의 수를 구하는 문제인데, 어떻게 풀어야 할까?

dp로 접근해보자.
d[n] = n명의 사람을 지그재그 형태로 세울 수 있는 경우의 수...?
근데 앞에서 어떤 키의 사람이 어떻게 서있냐에 따라 뒷 부분이 달라진다...
예를 들어, 1~5까지 있을 때, 5, 4가 먼저 섰다면 뒤에는 4보다 큰 사람이 와야하는데 없다...
그렇다면 필요한 정보는 앞에 두 사람의 정보가 필요할 것 같다.
d[pre1][pre2][n] = 앞에 두 사람이 pre1, pre2일 때 n번째 사람을 결정할 차례일 때, 지그재그 형태로 세울 수 있는 경우의 수...

그리고 하나 더 줄을 서지않고 남아있는 사람의 수도 알아야 한다. 같은 d[pre1][pre2][n]일지라도 앞에 누가 섰냐에 따라 달라지기 때문에... 그렇다고 n이 100인데 그 상태를 갖고 다니기에는 너무 크다...

다르게 접근해야 할 것 같다.
생각해보다가 떠오른 것이 이 문제는 경우의 수 dp문제인데...
구하는 방법 중에 전체 경우에서 아닌 경우를 빼는 방법이 있다. 한 번 이 방법으로 생각을 해보자. 아닌 경우라 하면, 완벽한 지그재그가 아닌 경우의 수인데... 이 것도 그리 쉽게 구할 수 있을 것 같진 않다...

그냥 질문 검색을 보기로 했다.
유카리코(yukariko )님의 친절한 설명이 답변으로 나와있다.

문제가 되는 부분이 앞에 누가 섰느냐에 따라 달라지기 때문에 줄을 서지 않은 사람을 알아야 한다는 것인데, n이 작다면 bitmask를 이용해서 상태dp를 사용할 수 있지만, n이 너무 크다.
하지만 어떤 사람이 서있고, 아직 서지 않은 사람을 아는 대신, 한 사람에 대해서 그 사람보다 작은 사람의 수, 큰 사람의 수만 알고 있어도 된다.
과연 이 정도 정보만으로 모든 경우를 구별해서 memoization이 잘 될까?
생각해보면 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우는 여러 경우가 있을 수 있지만, 확실한 것은 어떤 사람보다 작은 사람의 수와 큰 사람의 수가 같은 경우들은 모두 그 경우의 수가 같을 것이라는 것이다. 아 물론 한가지 조건이 더 필요하다. 그 어떤 사람의 다음에 올 사람이 더 작은 사람인지 더 큰 사람인지에 대한 정보만 있으면 그 경우의 수는 같을 것이다. 
모든 사람의 키는 다 다르고, 줄을 세울 때, 큰 사람, 작은 사람, 큰, 작은,... 순으로, 즉 단순히 크기의 비교로만 세우는 것이기 때문에 현재 어떤 사람까지 세웠고, 그 사람보다 작은 사람이 몇 명 있는지와 큰 사람이 몇 명 있는지, 그리고 그 사람 다음에 더 큰 사람이 와야하는지 아닌지에 대한 정보만 같다면 그 사람이 누군지에 상관없이 그 사람 뒤로 줄을 세울 수 있는 경우의 수는 같을 것이다.
그리고 또한, 작은 사람의 수, 큰 사람의 수를 알고 있다면 그 사람이 몇 번째로 줄 서는지도 자동으로 알 수 있다.(즉, 몇 번째인지는 안 넣어도 구분이 된다)

와... 정말 기막힌 방법이다. 단순히 크기 비교로 줄을 세우기 때문에, 어떤 사람을 세우고, 그 사람뒤에 큰 사람이 올지 작은 사람이 올지와 그 사람보다 작은 사람의 수와 큰 사람의 수만 알면...구분이 가능하다...전혀 생각도 못했는데, 이렇게 알고나니 생각못할 건 아닌 것 같기도 하면서... 내 부족함을 또 느낀다. 하지만 이제 문제를 많이 풀기로 결심한 만큼 좌절하지 않고 이런 문제를 다음에는 틀리지 않는 것을 목표로 이렇게 정리도 하고 있고, 계속 빠르게 풀어나가야 겠다.

d[small][big][next] = 현재 사람보다 작은 사람이 small명, 큰사람이 big명이고 다음에 올 사람이 현재 사람보다 next(크거나 작은)한 사람이 올 경우 경우의 수
첫번째 위치에 1부터 n까지의 사람이 서는 경우에 대하여 next는 두가지 경우 모두에 대해서 경우의 수를 구해서 합치면 될 것이다.
구현해 봐야겠다. 
다음 사람을 고를 때, 어떤 사람을 고르느냐에 따라 다음 사람의 small, big이 달라지게 된다.
제출해서 한 번 틀렸는데, 원인이 n이 1일때는 답이 1이 나와야 하는데 내 코드에서는 2가 나온다. 그래서 n이 1인 경우만 예외처리를 해줘서 AC를 받았다.!

그리고 이와 비슷한데 n이 작아 bitmask dp로 풀 수 있는 문제도 추천해 주셨다.

참고 및 출처 : https://www.acmicpc.net/board/view/3358