백준 Baekjoon 2616번 소형기관차 - JAVA 문제 풀이 다이나믹 프로그래밍과 누적합을 사용하여 푸는 문제이다. 제한사항의 기관차의 수가 그리 크지 않어 dfs탐색으로도 풀 수는 있을거 같지만, 시간이 오래걸리고 문제에서 원하는 풀이 방식은 아닌듯 했다. 누적합을 사용하여 뒤에 DP에서 기관차가 끌 수 있는 최대 객차의 수의 승객의 합을 쉽게 구할 수 있다. DP의 점화식은 다음과 같다. dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + sum[j] - sum[j - max]) i를 1 ~ 3 범위로 증가 시키며 각 숫자의 기관차가 운송할 수 있는 최대의 손님 수를 구한다. j를 i * max의 범위부터 시작하는데, 예시로 주어진 문제를 예로 들어..