문제 본문
참고가 많이 되었던 해설
https://amunre21.github.io/boj/1-1912/
https://st-lab.tistory.com/140
자체 해설
결론은 혼자 힘으로 풀지 못했다.
문제점 진단
"누적합"이라는 컨셉은 이해가 되었는데,
"연속되는 몇개의 수를 선택해서 구할 수 있는 합" 중에 "가장 큰 값"을 구하는 부분을 이해하고 구현하는게 어려웠다.
- 탐색하며 누적합을 만들며, 누적합이 가장 큰 경우가 발견될 때마다 곧장 랭크한다. (메모이제이션)
- 현재의 누적 합과 현재 탐색 중인 값을 비교한 결과, 더 작은 경우 누적합의 랭크 기록은 유지하되, 탐색 중인 값부터 누적한다. (DP > Bottom-Up)
요약
- 탐색 과정에서 누적의 합은 기억한다.
- 단, 그 과정에서 현재의 누적 합보다 현재 탐색 값이 클 경우, 기존 누적의 합은 무시하고 현재의 탐색 값부터 누적한다.
Hi!