문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.


솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.



D.P 문제 중에는 난이도가 낮은 문제가 아닐까?

반응형

설정

트랙백

댓글