백준 25822 2000문제 푼 임스

문제

스트릭 프리즈를 2번만 써서 스트릭 유지 일수가 최대로 유지될 수 있는 경우를 구하는 문제이다. 모든 경우의 수에서 최선을 찾아야 하므로 다이나믹 프로그래밍을 이용해서 풀어야했다.

처음에는 i날일 때, 문제를 푼 날과 풀지 않은 날로 2차원 배열을 만들어 각각 저장했는데, 그렇게 하다보니 제대로 되지가 않았다. 점화식을 쓸 때부터 막혀서 한참 고생했다.

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 coin = +inputs[0];
const N = +inputs[1];
const problems = inputs[2].split(" ").map(Number);
 
const maxFreeze = Math.min(Math.floor(coin / 0.99), 2);
 
// dp[i][j] = i일째까지, j개의 스트릭 프리즈를 사용했을 때의 최대 스트릭 길이
const dp = Array.from({ length: N }, () => Array(maxFreeze + 1).fill(0));
 
for (let f = 0; f <= maxFreeze; f++) {
  dp[0][f] = problems[0] > 0 ? 1 : f >= 1 ? 1 : 0;
}
 
let maxProblems = problems[0];
 
for (let i = 1; i < N; i++) {
  maxProblems = Math.max(maxProblems, problems[i]);
  if (problems[i] > 0) {
    for (let f = 0; f <= maxFreeze; f++) {
      dp[i][f] = dp[i - 1][f] + 1;
    }
  } else {
    // 문제를 풀지 못한 날
    for (let f = 0; f <= maxFreeze; f++) {
      // 스트릭이 끊어지는 경우
      dp[i][f] = 0;
 
      // 이전 상태에서 스트릭 프리즈를 새로 사용하는 경우
      if (f > 0) {
        dp[i][f] = Math.max(dp[i][f], dp[i - 1][f - 1] + 1);
      }
    }
  }
}
 
// 최대 스트릭 길이 찾기
let maxStreak = 0;
for (let i = 0; i < N; i++) {
  for (let f = 0; f <= maxFreeze; f++) {
    maxStreak = Math.max(maxStreak, dp[i][f]);
  }
}
console.log(dp);
 
console.log(maxStreak);
console.log(maxProblems);
 

f가 스트릭을 사용한 개수라고 할 때, 스트릭 프리즈를 새로 사용하는 경우는 이전 스트릭을 사용하기 전일 때 최대 개수와 지금의 값과 비교한 뒤 갱신시키면 된다.

마지막에는 최대 스트릭 길이를 찾기 위해 이중루프로 2차원 배열을 전부 돌면서 최댓값을 찾았다.