moonsoo5522   7년 전

처음에는 점화식을 dp[현재 숫자][지나온 경로(bitmask)][방향]으로 정의해서 풀려고 했는데,


현재 숫자를 고려하다보니 메모리 초과가 예상되더라구요.


그래서 차원을 하나 줄여서 dp[지나온 경로(bitmask)][방향]으로 정의해서 풀려고 생각해봤지만, 예외 상황이 있더라구요.


현재까지 지나온 경로가

4 1 2

2 1 4

일 경우, 현재 숫자를 고려하지 않는다면 위 두 경로는 상태공간이 정확히 일치하게 되는데,

실제로 보면 4 1 2의 경우 2보다 작은 수가 더이상 없는 데에 반해, 2 1 4는 다음 숫자로 3을 선택할 수 있기 때문에 위 점화식이 완전하지 않다는 걸 발견했습니다.


그래서 아래 코드의 주석처리된 부분을 통해, 더이상 진행할 수 없는 경우를 체크해서 0을 리턴하는 방식으로 짜봤는데,,, 입력값이 커지면 제대로 값이 나오지 않더라구요..


여기서 더이상 진전이 없는데 혹시 bitmask dp로 풀 수 없는건지, 제가 실수를 한 건지 잘 모르겠네요..


지그재그 서기 문제처럼 3차원 dp로 푸는 방법도 있겠지만, 충분히 비트마스크 디피로도 해결할 수 있을거라 생각하고 도전했는데 힘드네요..

yclock   7년 전

먼저 dp[현재 숫자][지나온 경로][방향] 에서 "현재 숫자" 정보를 제거하는 것은 무리 같습니다...

그러나 "방향" 정보는 필요하지 않습니다.

그냥 두 번째 병사가 무조건 이웃한 병사보다 키가 작도록 가짓수를 구한다고 생각하고 답을 구했다면, 정답은 그 값의 2배입니다.(N=1은 예외)

이는 위와 같은 방향으로 줄을 서는 방법과 반대 방향으로 줄을 서는 방법이 일대일대응이 가능하기 때문입니다.

예를 들어, N=6일 때 줄을 {3, 1, 6, 4, 5, 2}와 같이 섯다고 하면, 각 값과 (N+1)과의 차를 구함으로써 {4, 6, 1, 3, 2, 5}로 변환할 수 있습니다.


좌우지간 dp[현재 숫자][지나온 경로]만 이용하면, 처음 방법보다는 메모리를 1/2배 사용하겠군요... (그래도 메모리 초과가 됩니다.)

moonsoo5522   7년 전

이 방법으로는 좀 힘들겠군요... 감사합니다 ㅠㅠ

h0ngjun7   7년 전

홍준이...

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