algoshipda   1년 전

처음엔 세로줄을 모두 채우고 바꿔가면서 최대를 찾는 식으로 했는데 이게 답을 못내린다는걸 알았습니다.

한 학생이 앉으면 거기서 4방향에 다른 학생이 못앉지만 대신 왼쪽부터 채워나가는 식으로 하면

왼쪽 위, 왼쪽만 보면 된다고 생각했는데 이렇게 하려니 앞에 앉는 경우에 따라 뒤에 결과가 다르게 나와서 어떤식으로 풀어야 될지 모르겠네요.

세로줄이 최대 10개까지 가능하므로 세로에 앉힐 수 있는 경우의 수는 1024개고 왼쪽부터 채워나갈땐 왼쪽거만 보면 되니깐

10 * 1024 * 1024 이 정도로 풀 수 있을거 같기도 해서 해보려고 했는데 저 조합을 어떻게 배열로 표현해야 될지 모르겠네요

힌트 좀 주세요

appa   1년 전

상태 공간은 N*(2^N)개이면 충분하고 저 같은 경우에는 10 * 10 * 1024 * 1024의 시간복잡도로 풀었었네요

algoshipda   1년 전

왼쪽줄, 오른쪽줄에 어느 위치에 앉았다 안앉았다를 어떻게 배열의 인덱스로 표현하죠? int에 비트연산 해야하나요?

appa   1년 전

네. 0~n-1번째 자리를 2^i(0<=i<=n-1)로 생각하면되요.

algoshipda   1년 전

아하 감사합니다 한번 풀어볼게요

appa   1년 전

참고로 덧붙이자면, 저는 학생이 앉아있는 상태를 가지고 bitmask dp로 풀었는데, 인접하게 앉아있는 경우는 애초에 불가능한 경우라 그런 상태는 고려하지 않으면 2^10보다 훨씬 작은 숫자로 줄어듭니다.

appa   1년 전

O(N^2 * 상태^2)이네요.

algoshipda   1년 전

감사합니다 풀었습니다 시간 1.9초 정도로 턱걸이했습니다

tkim0723   1년 전

hongjun7님께 질문이 있는데 메일주소하나 알수있을까요?

appa   1년 전

개인적인 질문이 아니라면 여기 게시판에 글을 쓰시고 [email protected]'로 태그해주시면 답글해드리겠습니다. 만약 그렇다면, [email protected] 메일주세요.

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