2616 (1) [백준 2616] 소형기관차 문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 문제는 크게 dp를 사용해 풀이한다. 하지만 누적합의 개념도 적용된다. 누적합 문제를 풀기 위해선 누적합을 통해 점화식을 작성해야 한다. 누적합이란 Prefix Sum이라 불린다. 말 그대로 해당 구간에 대해 누적된 합을 구하는 알고리즘이다. 배열의 값이 바뀌지 않는다는 조건이 있을 때 적용이 가능하다. 자신의 인덱스 값과 이전 인덱스 값을 더하며 구현한다. 예를들어 [1, 3, .. 이전 1 다음
