99클럽 코테 스터디 18일차 TIL - 강아지는 많을수록 좋다 (dp)

문제: https://www.acmicpc.net/problem/27971

접근 방식

• 상태 정의: dp[i]는 i마리의 강아지를 만드는 데 필요한 최소 행동 횟수를 의미
• 초기 상태: 처음에는 강아지가 0마리이므로 dp[0] = 0
  • 나머지 상태는 아직 도달할 수 없으므로 Infinity로 초기화

// 점화식
dp[i + a] = min(dp[i + a], dp[i] + 1)  // a마리 추가하는 경우
dp[i + b] = min(dp[i + b], dp[i] + 1)  // b마리 추가하는 경우

• 특별 처리: 만약 i + a 또는 i + b가 금지된 구간에 속한다면 강아지가 모두 사라지므로 dp[0]을 갱신
  dp[0] = min(dp[0], dp[i] + 1)

문제풀이

const fs = require('fs')
const [[n, m, a, b], ...arr] = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map((s) => s.split(' ').map(Number))

const forbiddenRanges = []

// 금지된 범위 저장
for (let i = 0; i < arr.length; i++) {
  const [l, r] = arr[i]
  forbiddenRanges.push([l, r])
}

// 금지된 강아지 수 배열 생성
const forbidden = new Array(n + 1).fill(false)
for (const [l, r] of forbiddenRanges) {
  for (let i = l; i <= r; i++) {
    forbidden[i] = true
  }
}

// N이 금지된 범위에 속하는지 확인
if (forbidden[n]) {
  console.log(-1) // n마리를 만들 수 없음
  process.exit(0)
}

// DP 배열 초기화: dp[i]는 i마리의 강아지를 만드는데 필요한 최소 행동 횟수
const dp = new Array(n + 1).fill(Infinity)
dp[0] = 0 // 처음에는 강아지가 0마리

// 각 상태를 순회하며 DP 테이블 채우기
for (let i = 0; i < n; i++) {
  // 현재 강아지 수 i마리에서 행동할 수 있는 경우만 처리
  if (dp[i] === Infinity) continue

  // A 마법 사용
  const nextA = i + a
  if (nextA <= n) {
    if (!forbidden[nextA]) {
      // 금지된 범위에 속하지 않으면 강아지 추가
      dp[nextA] = Math.min(dp[nextA], dp[i] + 1)
    } else {
      // 금지된 범위에 속하면 강아지가 모두 사라짐 (0으로 리셋)
      dp[0] = Math.min(dp[0], dp[i] + 1)
    }
  }

  // B 마법 사용
  const nextB = i + b
  if (nextB <= n) {
    if (!forbidden[nextB]) {
      // 금지된 범위에 속하지 않으면 강아지 추가
      dp[nextB] = Math.min(dp[nextB], dp[i] + 1)
    } else {
      // 금지된 범위에 속하면 강아지가 모두 사라짐 (0으로 리셋)
      dp[0] = Math.min(dp[0], dp[i] + 1)
    }
  }
}

// 결과 출력 - 도달할 수 없다면 -1 출력, 아니면 최소 행동 횟수 출력
if (dp[n] === Infinity) {
  console.log(-1)
} else {
  console.log(dp[n])
}