jungby1   2년 전

첫번째 예시는 잘 돌아갑니다. 계산과정도 출력해보니 제 논리구조랑 같은것 같습니다. 논리구조는 dp를 이용해서 가장 작은 합+그 수열의 전체 합을 구해

서 풀었습니다. 그런데 이상하게 두번째 예시만 넣으면 1095가 나옵니다.. 도데체 뭐가 잘못된걸까요.. 숫자개수가 15개라 그런지 어디서 틀린지 감을 잡기가 

힘드네요;;

15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

정답; 864  내 답; 1095

dudlf016   2년 전

dp[k][k+i]가 전체 경우의 수에서 최소값을 저장하는게 아니라

반복문의 마지막 두 가지 경우에서의 최소값을 저장하게 되서 그렇습니다.

아래는 계산과정 그대로 출력한 결과입니다.

15 

1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

--------- sum 1 ~ 15 : 268--------
min(d[1][1] + d[2][15], d[1][2] +  d[3][15]) = min(0 + 1065 = 1065, 22 +892 = 914) = 914
min(d[1][2] + d[3][15], d[1][3] +  d[4][15]) = min(22 + 892 = 914, 47 +864 = 911) = 911
min(d[1][3] + d[4][15], d[1][4] +  d[5][15]) = min(47 + 864 = 911, 58 +831 = 889) = 889
min(d[1][4] + d[5][15], d[1][5] +  d[6][15]) = min(58 + 831 = 889, 90 +766 = 856) = 856
min(d[1][5] + d[6][15], d[1][6] +  d[7][15]) = min(90 + 766 = 856, 159 +582 = 741) = 741
min(d[1][6] + d[7][15], d[1][7] +  d[8][15]) = min(159 + 582 = 741, 204 +552 = 756) = 741
min(d[1][7] + d[8][15], d[1][8] +  d[9][15]) = min(204 + 552 = 756, 246 +529 = 775) = 756
min(d[1][8] + d[9][15], d[1][9] +  d[10][15]) = min(246 + 529 = 775, 292 +512 = 804) = 775
min(d[1][9] + d[10][15], d[1][10] +  d[11][15]) = min(292 + 512 = 804, 340 +399 = 739) = 739
min(d[1][10] + d[11][15], d[1][11] +  d[12][15]) = min(340 + 399 = 739, 524 +167 = 691) = 691
min(d[1][11] + d[12][15], d[1][12] +  d[13][15]) = min(524 + 167 = 691, 664 +94 = 758) = 691
min(d[1][12] + d[13][15], d[1][13] +  d[14][15]) = min(664 + 94 = 758, 778 +49 = 827) = 758
min(d[1][13] + d[14][15], d[1][14] +  d[15][15]) = min(778 + 49 = 827, 931 +0 = 931) = 827
---------- d[1][15] : 1095 -----------


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