선생님 안녕하세요? 질문이 있어서 댓글 남겼습니다. 

저는 dp(i, j) = min(dp(i,k) + dp(k+1,j) )와 같은 점화식을 찾았지만, 어떻게하면 비용을 누적시킬 수 있을까 하는 문제를 해결하지 못하여 생각에 올려주신 코드를 참고했습니다.

혹시 preSum 이라는 부분이 있던데, 이 부분이 비용 누적과 관련된 코드로 보여지고 또 이 부분이 저로서 이해가 쉽게 되지 않습니다 ㅠㅠ

이 부분에 대해서 조금이나마 설명해주시면 정말 감사하겠습니다! 

@chrismrkr

예를들어 [10, 20, 30, 40] 구간이 있다고 할 때

[10, 20], [30, 40] 구간으로 합치는 경우가 최소 라고 해봅시다.

그러면 이때 소요되는 총 비용은

1. [10 + 20], [30 + 40] // 각 부분을 따로따로 합쳐줌

2. [10, 20] + [30, 40] // 각 부분을 하나로 합쳐 줌

이렇게 2단 계로 구성됩니다.

따라서 preSum 은 [a ~ b] 구간을 [a ~ i], [i+1 ~ b] 구간으로 나누어 합칠 때

2번 과정인 [a ~ i], [i+1 ~ b] 구간을 [a ~ b] 로 합쳐주는 과정에서 더해지는 [a ~ b] 구간의 합을 의미합니다.

현재 구간을 나눌 때, 언젠간 다시 현재 구간으로 합칠 테니 현재 구간의 합 을 미리 더해주고 부분 문제로 쪼개는 것 이라고 생각하시면 됩니다.

감사합니다. 해결했습니다 !^^

최근 질문 게시판 게시글 중 최고네요 아이디어를 얻어갑니다.