백준 2616 < 소형 기관차 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/2616

2616번: 소형기관차

 

📍알고리즘 분류

- 다이나믹 프로그래밍

- 누적 합

 

📍문제 풀이

- 연속된 수열이 주어지고, 1 ~ 3 사이의 자연수 max가 하나 주어진다

- 연속된  수열에서 max 개의 연속하는 수를 3개 만들고, (겹치면 안됨)

그 합이 최대가 되는 수를 구하라 

 

⭐연속된 수열에서 구간 합을 빠르게 구하기 위해 누적 합 (prefix sum) 배열을 만들고 이용한다

- 예를 들어

      1    2     3     4      5     6    7

     35 40   50   10   30   45   60 수열이 주어질 때, 누적 합 배열 S는

  0 35 75 125 135 165 210 270

 

2 에서 4 까지의 구간 합을 구하려면

S[4] - S[1] 을 구해주면 된다

 

테이블 형태로 문제를 풀어보면 (소형차가 끌 수 있는 객차 수 = 2)

소형차 번호 = i객차 번호 = j

승객수		35	40	50	10	30	45	60
누적합	0	35	75	125	135	165	210	270
0번 소형차최대 객수	0	0	0	0	0	0	0	0
1번 소형차최대 객수	0	0	75	90 (125 - 35)	90	90	90	105
2번 (1번의 결과에서 연속)	0	0	0	0	135 (75 + 60)	135	165 (90 + 75)	195 (90 + 105)
3번	0	0	0	0	0	0	210 (135 + 75)	240 (135 + 105)

 

⭐포인트
1️⃣이전 값과 비교한 최댓값을 j 번의 값으로 정함

2️⃣소형차 번호가 늘어날 때, 이전 소형차가 점유한 공간을 확보해줘야 하기 때문에, 시작 지점이 객차수 * 소형차 번호 만큼 밀림

 

이를 활용하여 점화식을 세우면 (max =소형차가 끌 수 있는 객차 수)

for (let i = 1; i <= 3; i++) {
    // i = 소형 기관차 번호
    for (let j = i * max; j <= N; j++) {
      // j = 소형 기관차가 운송을 시작할 수 있는 객차 번호
      memo[i][j] = Math.max(
        // 이전 값과 비교 -> 최댓값 가져가기 위해
        memo[i][j - 1],
        // memo[i - 1][j - max]
        // 현재 소형차 번호가 끌 수 있는 객차 수를 확보하기 위해
        // 이전 소형차 번호는 max 만큼 이전 것을 사용
        // 우측은 구간합
        memo[i - 1][j - max] + (prefixSum[j] - prefixSum[j - max]),
      );
    }
  }

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input[0];
  const data = input[1].split(" ").map(Number);
  const max = +input[2];
  const prefixSum = [0];
  // memo 2차원 배열 생성
  // N + 1 만큼 0으로 채운 배열이 4개 있는 배열
  const memo = Array.from({ length: 4 }, (_) =>
    Array.from({ length: N + 1 }, (_) => 0),
  );
  // prefix sum 생성
  for (let i = 1; i <= N; i++) {
    prefixSum[i] = prefixSum[i - 1] + data[i - 1];
  }
  // 점화식 생성
  for (let i = 1; i <= 3; i++) {
    // i = 소형 기관차 번호
    for (let j = i * max; j <= N; j++) {
      // j = 소형 기관차가 운송을 시작할 수 있는 객차 번호
      memo[i][j] = Math.max(
        memo[i][j - 1],
        memo[i - 1][j - max] + (prefixSum[j] - prefixSum[j - max]),
      );
    }
  }
  console.log(memo[3][N]);
});

 

📍리뷰

- 이런 DP 문제를 풀 때 테이블을 그려서 풀면 편하다!