isvara   8일 전

bitmask dp.. 어떤식으로 정의하고 풀어야할지 감이 전혀 안잡히는데 bitmaks dp로  푸신분 혹시 조금만 힌트라도 알려주실 수 있을까요..?

djm03178   8일 전

dp[i][x]를

i-1번째 행에 사람이 앉아있는 상태를 0과 1로 표현한 값이 x일 때, i번째 행부터 마지막 행까지 앉을 수 있는 사람의 최대 수

로 정의해 보세요.

isvara   8일 전

조언대로 우선 짜봤는데, 제가 비트마스크를 처음 써봐서 그런지 에러가 많이 나옵니다..

특히 solve함수안에 for문이 반복을 하지가 않네요..

코드설명을 덧붙히면  전달받은 state로 다음 행에 둘 수 없는 위치 정보를 주기위해서 cunning변수를 두고 현재 state에서 맨 왼쪽 비트를 제거하고 왼쪽으로 한칸 땡긴 집합과

state에서 오른쪽으로 한칸 땡긴 집합을 합집합해서

 101010으로 두었다고 치면

010101로 다음값에 주려고 계산을 했습니다.

그 이후에 cunning과 이전에 계산해두었던 broken으로 부서진 위치 까지 만들 수 있는 집합에서 제외시키고 재귀를 호출 했는데

혹시 잘못된 지점 있으면 따끔하게 부탁드립니다. ㅜ..

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