skyinyour   6년 전

제가 도저히 접근을 못하겠어서 다른분들 코드를 보고 공부하고 있습니다.

대충 이해는 가는데 도저히 이해가 안가는 부분이 있어 질문드립니다.

dp[start][end] = INF;

for (int i = start; i <= end; i++) {
int tmp = f(start, i) + f(i + 1, end) + sum[end]-sum[start-1];
dp[start][end] = min(dp[start][end], tmp);
}


여기서 dp[start][end] 에 INF를 집어넣고 tmp와 비교하면 항상 tmp가 작을 텐데 굳이 왜저렇게 매번 INF를 넣어주고 비교하나요??


djm03178   6년 전

dp[start][end]에 들어가는 값은 반복문을 다 돌렸을 때 나온 최솟값을 담아야 합니다. 그걸 위해서 tmp를 하나 얻을 때마다 min을 갱신해주는 거고요.

그런데 INF를 안 담으면, 처음에 dp[start][end]는 -1로 초기화되어 있으니, min(dp[start][end], tmp)는 tmp가 무슨 값이 되든 항상 -1로 남게 됩니다. 이걸 방지하기 위해서 무조건 처음에는 tmp로 값이 갱신되도록 해주기 위해 INF를 넣어주고 시작하는 것입니다.

skyinyour   6년 전

감사합니다 :) 겨우겨우 이해했습니다 ㅠㅠ

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