mhccc   5년 전


15번 줄의 코드에서 d[i]와 d[i-j]+a[j]를 비교해도 정답이 되는 것인지가 의문입니다. d[i-j]와 d[j]를 더해서 최대값을 비교해야 하는 것 아닌가요??

제가 이렇게 생각한 이유는 a[j]의 값보다 d[j]에 더 최적화된 최대 판매량이 이미 저장되어 있을 것이기 때문입니다.

만약에 a[j]에 저장된 값이 3이고 d[j]에 저장되는 값이 3보다 크다면 위와 같은 식은 틀린 것이 될 것 같은데 제가 잘못생각하고 있는 것이 무엇인가요???

어째서 저 식으로 반례없이 정답이 나오게 되는지 이해가 되질 않습니다.

Green55   5년 전

a[4] = 3이고 d[2] = a[2], d[4] = d[2] + a[2] = 4 같은 케이스를 생각하시는거 같은데요.

굳이 d[5] = d[1] + d[4]로 갱신 하지 않아도,

d[4] = d[2] + a[2], d[5] + d[4] + a[1] 같은 경로로 인해 이런 케이스도 예외 없이 처리됩니다.

물론 점화식을 max(max(d[i],a[i]),d[i-j]+d[j]))로 사용해도 정답을 얻을 수 있습니다.

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