백준 2616 소형 기관차

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

문제

소현 기관차가 겹치지 않으면서 최대한의 승객을 수용할 수 있도록 할 수 있는 경우의 수를 구하는 문제이다. 객차의 수는 50000이하의 범위까지 있으므로 백트래킹과 같은 완전탐색 방식으로 풀기에는 시간이 너무 오래 걸린다.

따라서 dp를 이용해서 해당 문제를 풀어야 한다.

dp 배열과 점화식 생각해보기

소형 기관차는 3개로 고정되어 있기 때문에 배열을 dp[i][j] = 소형기관차 i개까지 선택하고 j번째까지 고려했을 경우 가지는 최대 승객의 수로 생각해보면 dp[3][n]의 경우 3개의 소형기관차로 선택함과 동시에 n까지의 객차를 고려했을 때 가질 수 있는 최대 승객의 수를 넣을 수 있다.

그렇다면 점화식의 경우엔 고려해야 할 경우가 두 가지가 있다.

• 소형 기관차가 추가되어 j번째 객차 추가
  • dp[i-1][j-m] + sum[j] - sum[j-m]
  • 소형기관차는 최대 m개의 객실을 끌 수 있다
  • 그러므로 객차를 추가하는 경우는 이전 소형기관차 i-1번째까지 선택하고 j-m만큼 고려했을 때 나온 최댓값에 m+1부터 j까지 고려했을 때 가지는 합을 더하면 소형 기관차를 i개까지 선택하면서 j번째까지 고려했을 경우 가지는 최대 승객 수이다.
• 소형 기관차가 추가되어 j번째 객차 추가도 안됨
  • 이전에 계산했던 범위이기 때문에 dp[i][j-1]로 접근하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +inputs[0];
const trains = inputs[1].split(" ").map(Number);
const trainLimit = +inputs[2];
 
const dp = Array.from({ length: 4 }, () =>
  Array.from({ length: n + 1 }, () => 0)
);
 
const sum = [0];
for (let i = 1; i <= n; i++) {
  sum.push(sum[i - 1] + trains[i - 1]);
}
 
for (let i = 1; i <= 3; i++) {
  for (let j = trainLimit; j <= n; j++) {
    dp[i][j] = Math.max(
      dp[i][j - 1],
      dp[i - 1][j - trainLimit] + sum[j] - sum[j - trainLimit]
    );
  }
}
console.log(dp[3][n]);
 

진심 dp적 사고 너무 어렵다.. 처음에 dp[i][j]를 어떻게 구성하고 점화식을 이끌어내는 과정이 너무 생각이 안 났던 것 같다. 요 부분을 다른 dp 문제들을 풀면서 계속 반복훈련을 시켜야 될 듯 하다.