chatterboy   1년 전

어떻게 접근해야 할지 모르겠어요.

현재까지 뽑은 수인지 확인하는 배열 picked[N] 없이 어떻게 해야할까요?

yukariko   1년 전

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

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


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

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개가 됨을 알 수 있지요.


yukariko   1년 전

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

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

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

chatterboy   1년 전

yukariko

아하! 답변 감사합니다.

goodksj   6달 전

yukariko


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


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


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


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


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


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



yukariko   6달 전

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

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

만약 1 3중에 1을뽑으면

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

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

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

댓글을 작성하려면 로그인해야 합니다.