sds901234   3년 전

11066번 파일합치기 문제를 풀어보았는데 도저히 풀 수 없어서 구글링을 좀 해보았는데요..

검색결과 점화식은 

DP[i][j] = min(i <= k < j){ DP[i][k] + DP[k + 1][j] } + partialSum(i, j)

인 것으로 파악했는데요..

먼저 위 식이 11066번의 예제 입력에 대해서는 올바르게 작동하는 것을 알겠습니다.

DP[1][4] = D[1][2] + DP[3][4] + partialSum(1, 4)

하지만 제가 생각한 다른 입력에 대해선 맞지 않아 이게 맞는건지 혼란스럽습니다.

예를 들어 40, 30, 30의 배열에 대해

DP[1][3] = min(1 <= k < 3){DP[1][k] + DP[k + 1][3]} + partialSum(1, 3)

               = min{DP[1][1] + DP[2][3], DP[1][2] + DP[3][3] } + partialSum(1, 3)

               =min( (40 + 60), (70 + 30) ) + (40 + 30 + 30)

               =200

하지만 최적해는 30 + 30 = 60,  60 + 40 = 100, 총 합은 160인데요

어디서 잘못된걸까요

도와주세요 ㅠㅠ


jh05013   3년 전

DP[1][1]과 DP[3][3]은 0입니다.

sds901234   3년 전

아....!
생각해보니 그러네요.....ㅡ_ㅡ
감사합니다...ㅠㅠ

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