2256번 - 젓가락
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 님께 힌트도 들었는데 잘 모르겠네요...
D(i,j) = min( D(i,j+1), D(i-1,j+2) + |X(j) - X(j+1)| ^2 )
힌트는 여기까지
크... j 범위를 N - 3*i +1 부터 1까지 감소하면서 돌려주면 다 자동으로 처리되는 거 였군요...
좋은 문제네요ㅋㅋㅋ
aabbab 같은 경우가 어떻게 aa랑 bb가 안겹치고 처리되나 궁금했는데 사실 aa와 bb만 안겹치면 뒤에 a와 b는 자동적으로 결정이 되는군요ㅎㅎ
내가 생각해도 저건 개쩌는 힌트였음...우왕ㅋ
제가 처음 세웠던 dp 방향으로는 안되더라구요ㅋㅋ 저렇게 역방향으로만 생각해야지 풀 리는 것 같아요ㅋㅋ
댓글을 작성하려면 로그인해야 합니다.
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 님께 힌트도 들었는데 잘 모르겠네요...