[백준] 19621 회의실 배정 2 : 자바스크립트(node.js)

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

 

문제

서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.

 

입력

첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 N + 1 줄까지 공백을 사이에 두고 회의의 시작시간, 끝나는 시간, 회의 인원이 주어진다.

 

출력

첫째 줄에 회의실에서 회의를 진행할 수 있는 최대 인원을 출력한다.

 

풀이 방법

dp문제...!!!

회의의 끝나는 시간과 시작하는 시간만 고려해주면 된다

즉 가장 최근의 회의가 끝난 시간보다 다음으로 선택될 회의가 시작하는 시간이 빠르면 안된다.

이 조건만 걸어서 최대 인원 total을 계속 저장해 가기

 

그리고 처음 풀었을때 80%지점에서 틀렸었는데 이 회의들이 반드시 시작시간 순서대로 들어올거라고 장담할 수 없다

그래서 회의 시작시간 기준으로 한번 소트를 돌려준 뒤 recur을 돌렸더니 맞았음 

 

그냥 백트래킹으로도 풀고 dp에 저장하는 방식으로도 풀었다

 

먼저 그냥 백트래킹 코드

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((e) => e.split(" ").map(Number));

const N = input[0][0];
const arr = input.slice(1);
let ans = 0;

const recur = (idx, end, total) => {
  if (idx > N) return;
  if (idx == N) {
    ans = Math.max(ans, total);
    return;
  }
  if (arr[idx][0] < end) {
    recur(idx + 1, end, total);
    return;
  }

  recur(idx + 1, end, total);
  recur(idx + 1, arr[idx][1], total + arr[idx][2]);
};

const solution = () => {
  arr.sort((a, b) => a[0] - b[0]);
  recur(0, 0, 0);
  console.log(ans);
};

solution();

 

그러니까 recur만 뜯어서 보면

idx : 현재 회의 인덱스

end : 가장 최근의 회의가 끝난 시간

total : 현재까지 최대 인원

인덱스가 전체 회의 수에 도달했을 때 total을 업데이트 해주는거고

다만 end를 들고다니면서 회의 시간이 적합해야 하고 그렇지 않다면 다음 회의로 넘겨버리기. 

const recur = (idx, end, total) => {
  if (idx > N) return;
  if (idx == N) {
    ans = Math.max(ans, total);
    return;
  }
  if (arr[idx][0] < end) { 
  	// 다음 회의의 시작 시간이 마지막 회의 끝난시간보다 이른 경우
    recur(idx + 1, end, total);
    return;
  }

  recur(idx + 1, end, total);
  recur(idx + 1, arr[idx][1], total + arr[idx][2]);
};

 

 

위의 내용을 그대로 dp배열에 저장하면서 풀이, 값을 계속 리턴해감

dp배열에 일단 모두 -1을 넣어두고 시작.

현재 인덱스의 회의를 선택할 경우와 선택하지 않을 경우의 인원 중 더 큰값을 dp에 저장하면서 리턴한다

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((e) => e.split(" ").map(Number));

const N = input[0][0];
const arr = input.slice(1);
let dp = new Array(N).fill(-1);

const recur = (idx, end) => {
  if (idx > N) return Number.MAX_SAFE_INTEGER;
  if (idx == N) {
    return 0;
  }
  if (arr[idx][0] < end) {
    return recur(idx + 1, end);
  }
  if (dp[idx] !== -1) {
    return dp[idx];
  }
  dp[idx] = Math.max(
    recur(idx + 1, arr[idx][1]) + arr[idx][2],
    recur(idx + 1, end)
  );
  return dp[idx];
};

const solution = () => {
  arr.sort((a, b) => a[0] - b[0]);
  console.log(recur(0, 0));
};

solution();

 

물론 이거보다 훨씬 간결한 풀이도 많겠지만...난 dp가 너무 어려웡