h0ngjun7   9년 전

O(KN^2)에서 잘 줄어들 지 않아서 고민입니다...

한 세트(?)를 고를 때, 가장 길이가 긴 젓가락이 없고, 2개씩만 골라서 |A-B|^2의 가중치가 든다면,

'D(i, j) = i번째 세트를 고르고, 길이순으로 젓가락들을 정렬했을 때 j번째까지의 가중치 합의 최솟값'이라 하면

D(i, j) = min( D(i, j-1), D(i-1,j-2)+|(X(i)-X(i-1)|^2 ) 이 됩니다.( X(i) : 젓가락들을 길이순으로 정렬했을 때, i번째 젓가락의 길이 )

여기서 i번째 세트에서 가장 길이가 긴 젓가락을 k번째라고 추가하면 O(KN^2)의 풀이가 나옵니다.

i번째에서 i번째와 i-1번째만을 참조하므로 토글링하여 메모리 문제는 줄일 수가 있겠습니다만 시간이....

도움 주시면 감사하겠습니다.

@pichulia 님께 힌트도 들었는데 잘 모르겠네요...

pichulia   9년 전

D(i,j) = min( D(i,j+1), D(i-1,j+2) + |X(j) - X(j+1)| ^2 )

힌트는 여기까지

h0ngjun7   9년 전

크... j 범위를 N - 3*i +1 부터 1까지 감소하면서 돌려주면 다 자동으로 처리되는 거 였군요...

좋은 문제네요ㅋㅋㅋ

h0ngjun7   9년 전

aabbab 같은 경우가 어떻게 aa랑 bb가 안겹치고 처리되나 궁금했는데 사실 aa와 bb만 안겹치면 뒤에 a와 b는 자동적으로 결정이 되는군요ㅎㅎ

pichulia   9년 전

내가 생각해도 저건 개쩌는 힌트였음...우왕ㅋ

h0ngjun7   9년 전

제가 처음 세웠던 dp 방향으로는 안되더라구요ㅋㅋ 저렇게 역방향으로만 생각해야지 풀 리는 것 같아요ㅋㅋ

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