DP, 누적합 문제https://www.acmicpc.net/problem/2616 이 문제는 냅색 알고리즘의 변형으로도 볼 수 있을 것 같다.누적합을 저장해준 (1차원) 배열을 만들고, 해당 배열을 활용하여 소형 기관차 3대로 최대 운송할 수 있는 손님수를 구하는 문제이다. 초기 접근 방식객차의 수, 소형 기관차가 최대로 끌 수 있는 객차의 수, 소형 기관차의 갯수(3)에 대한 정보가 주어졌다.처음에 이 문제를 보고 DP로 풀어야겠다고 생각했다. 그러나 초기에는 r = 소형 기관차가 최대로 끌 수 있는 객차의 수, c = 객차의 수에 대한 DP 배열의 형태를 구상하였기에 문제가 생각보다 쉽게 풀리지 않았다.3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다. 여기서 "최대"라는 말에 포커스..