백준 2240 자두나무

문제

T초 동안 떨어지는 자두를 받을 수 있는 최대 개수를 구하는 문제인데, 이동 횟수가 W번으로 제한되어 있어서 최적의 이동 경로를 찾아야 한다.
각 순간마다 최선의 선택을 해야 하므로 DP을 사용하면 효율적으로 해결할 수 있다.

dp 배열

• dp[i][j]: i초까지 진행했을 때 최대 j번 이동해서 받을 수 있는 자두의 최댓값을 저장한다.
• 이동 횟수가 j일 때,
  • j가 짝수이면 1번 나무에 있어야 하고,
  • j가 홀수이면 2번 나무에 있어야 한다.
• dp 테이블은 (T+1) x (W+1) 크기의 2차원 배열로 만들고, j를 기준으로 1번 나무와 2번 나무 중 최댓값을 갱신하면서 진행한다. 의 규칙을 통해 계속해서 해당 t초에서 가질 수 있는 최대의 자두 개수를 갱신해나간다.

점화식

각 시간 i에서 j번 이동한 경우,

• 자두가 1번 나무에서 떨어지는 경우:
  • j가 짝수일 때 받을 수 있음 → dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + 1
  • j가 홀수면 받을 수 없음 → dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])
• 자두가 2번 나무에서 떨어지는 경우:
  • j가 홀수일 때 받을 수 있음 → dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + 1
  • j가 짝수면 받을 수 없음 → dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])

즉, 현재 자두가 떨어지는 위치에 따라 최적의 값을 계속 갱신해 나간다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [t, w] = inputs[0].split(" ").map(Number);
const plums = [0, ...inputs.slice(1).map(Number)];
const dp = Array.from({ length: t + 1 }, () => new Array(w + 1).fill(0));
 
for (let i = 1; i <= t; i++) {
  //이동 없이 자두 받는 경우
  dp[i][0] = dp[i - 1][0] + (plums[i] === 1 ? 1 : 0);
 
  for (let j = 1; j <= w; j++) {
    //이동 횟수 짝수 -> 1번나무
    if (j % 2 === 0) {
      dp[i][j] =
        Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + (plums[i] === 1 ? 1 : 0);
    } else {
      //이동 횟수 홀수 -> 2번 나무
      dp[i][j] =
        Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + (plums[i] === 2 ? 1 : 0);
    }
  }
}
 
console.log(Math.max(...dp[t]));
 

사실 한 일년 전에도 제대로 못 풀었던 문제인데 이번에도 제대로 점화식을 생각 못해서 못풀었다… dp가 1차원 배열 정도일 때는 어찌어찌 잘 풀 수 있었는데 2차원 배열부터는 점화식을 도출해내기 너무 어려운 것 같다.