꼭 누굴 뽑았는지 알지 못해도, 자신을 기준으로 왼쪽에 몇명, 오른쪽에 몇명있는지를 계산할 수 있다면

동적계획법을 이용할 수 있습니다.

한가지 예를 들어보겠습니다.

5개의 숫자 1 2 3 4 5 가 있다고 할 때, 처음 두 수로 2, 4를 골랐다고 가정하면,

4의 왼쪽의 수는 1 2 3 중 2를 제외한 2개가 됩니다.

4의 오른쪽 수는 5로 1개가 되구요.

그 다음 수를 고를 땐, 2->4 였으므로, 4보다 작은 숫자를 골라야 하기 때문에 4의 왼쪽의 수 중 하나를 택하면 됩니다.

4의 왼쪽의 2개가 실제로 무슨 숫자였는지 몰라도, 그 다음 뽑을 숫자의 왼쪽과 오른쪽 수의 개수를 구할 수 있습니다.

만약 제일 왼쪽의 숫자를 고르면 그 숫자의 오른쪽 숫자는 4일 때 1개 였고, 4와 제일 왼쪽의 숫자 사이에 1개가 존재하기 때문에

다음 숫자의 왼쪽 숫자는 0개, 오른쪽 숫자는 2개가 됨을 알 수 있지요.

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

지그재그와 똑같은데 범위가 더 작은 문제입니다.

이 문제는 범위가 작아서 bitmask dp로 해결할 수 있습니다.

@yukariko

아하! 답변 감사합니다.

yukariko

님의 답변이 잘 이해가 가질 않습니다. 

지금 내가 뽑은 숫자를 기준으로 오른쪽 숫자와 왼쪽 숫자의 개수를 뽑는데 picked가 왜 필요 없는지 잘 모르겠습니다.

위의 님의 예시대로 2 4 를 뽑았으면

그 다음 숫자로 뽑을 수 있는 것은 1과 3입니다.

그럼 3을 뽑았다고 한다면 그 숫자의 남아 있는 왼쪽 숫자는 1밖에 없습니다. 2는 포함이 안되죠. 왜냐면 이미 뽑았으니까

이미 뽑은 것에 대한 정보가 있어야 지금 내가 뽑은 숫자를 기준으로 왼쪽과 오른쪽 숫자의 개수를 구할 수 있는 것 아닌지요?

1 3중에 3을뽑으면 왼쪽이 1, 오른쪽이 5인데 이것을 숫자로보지않고 개수로 봅니다.

그럼 왼쪽은 1개 오른쪽도 1개가 되겠죠.

만약 1 3중에 1을뽑으면

왼쪽이 0개 오른쪽이 2개가 됩니다.

이 예시는어디까지나 이해를 돕기위한것이고

왼쪽 오른쪽 개수만 가지고있어도 이러한 개수를 바로구할 수 있습니다. 위 예시를 개수만 가지고 다음 개수를 구할수있는 식을 떠올리면 됩니다.

@yukariko dp 처음공부하는 중인데요... 저도 윗분말처럼 이해가 안가요...

2 -> 4 뽑은다음에 그 다음 수를 1 or 3 중에 뽑는 상황이잖아요.

근데 방문한 표시가 없이 어떻게 3을기준으로 왼쪽이 1개, 오른쪽이 1개라고 아는거에요 ?

3기준으로 왼쪽(1, 2)니까 2개가 돼야 하고, 오른쪽도 (4, 5)니까 2개가 돼야하는거 같아서요. 

먼가 설명하실때 빠드리신 것 같은데 이해가능하게 설명해주실수 있을까요 ?