petil777   10달 전

dp[i][j] : i번째 숫자가 j번째 구간에 포함될 때 합이 최대인 구간의 합 이라고 정의해서

k<i인 k에 대해 dp[i][j]=max(dp[k][j-1], k+1번째 수부터~i번째 수까지의 합) 을 계속 갱신했습니다.

식을 잘못 세운 건가요? 아님 제가 문제이해를 제대로 못한건가요?

ntopia   10달 전

두 개의 구간이 서로 겹치거나 붙어 있어서는 안 된다.

이런 조건이 있는데 고려하지 않으신 것 같습니다.

petil777   10달 전

저는 구간이 붙어있다는 말의 의미를 [1, 3] [3, 5] 로 생각했습니다( 첫번째수~세번째수 세번째수~ 다섯번째수)

그런데 m<=n/2 조건을 보고 [1, 3] [4, ~] 이런 것도 붙어있는 것으로 간주해야 할 줄 알았는데 예시가 답이 9가 나온것을 보고 원래 생각한 것이 맞다고 느꼈습니다. 붙어있다는 의미가 둘 중 후자가 맞다면 어떻게 9가 나온 건지 설명좀 해주실 수 있나요? ㅠㅠ

6 2
-1
3
1
2
4
-1


ntopia   10달 전

아 자세히 보니 이거 점화식이 아예 잘못된 것 같습니다.

예제를 예로 들면

6 2

-1 3 1 2 4 -1

에서

-1 3 1 2 4 -1

요렇게 구간을 잡으면 구간에 속한 수들의 합이 9가 되어 최대가 되는 것 입니다.

petil777   10달 전

헉!!! 제가 문제 이해를 완전히 잘못했었군요 ;; 감사합니다!!

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