백준 JS 2457번 공주님의 정원 그리디

2457번: 공주님의 정원

첫 번째 시도

꽃이 지는 순서대로 정렬을 한 이후. 완전탐색으로 문제를 풀었다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const N = +input.shift()
const data = input.map(v => {
  const tempArr = v.split(" ")
  for(let i=0; i<4; i++){
    const str = tempArr[i]
    if(str.length === 1){
      tempArr[i] = "0" + tempArr[i] 
    }
  }
  return [tempArr[0]+tempArr[1],tempArr[2]+tempArr[3]].map(Number)
})
data.sort((a,b)=> a[1]-b[1])
const countArr = Array(N).fill(Infinity);
const answerArr = [];
for(let i=0; i<N; i++){
  const [str,end] = data[i]
  if(str <= 301){
    countArr[i] = 1
    continue;
  }
  for(let j=0; j<i; j++){
    const [str2,end2] = data[j]
    if(end2 >= str){
      if(countArr[i] > countArr[j] + 1){
        countArr[i] = countArr[j] + 1
      }
    }
  }
  if(end > 1130){
    answerArr.push(countArr[i])
  }
}
console.log(Math.min(...answerArr))

총 꽃의 개수가 10만개 이하 이므로, 완전 탐색을 하면 O^2으로 최대 100억번… 의 순회가 이루어 진다. 따라서 시간초과가 나올 수 밖에 없다.

---

두 번째 시도

그리디 문제임을 인지하고 시작.

1. 3월 2일 이전에 개화한 꽃들 중 가장 늦게 지는 꽃을 선택.
2. 선택된 꽃의 개화시기 부터 꽃이 지는 시기 까지의 날짜 중에 개화하는 꽃 중, 가장 늦게 지는 꽃을 선택
3. 2번을 반복
4. 반복 중 꽃이 지는 시기가 12월이 된다면 순회를 멈춘다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const N = +input.shift();
const data = input.map((v) => {
  const temp = v.split(" ");
  for (let i = 0; i < 4; i++) {
    if (temp[i].length === 1) {
      temp[i] = "0" + temp[i];
    }
  }
  return [temp[0] + temp[1], temp[2] + temp[3]].map(Number);
});
const bloomArr = Array.from({ length: 1200 }, () => 0);
for (let i = 0; i < N; i++) {
  const [str, end] = data[i].map(Number);
  if(bloomArr[str] < end){
    bloomArr[str] = end
  }
}
const flowerArr = [];
let choose = [];
for (let i = 1; i < 4; i++) {
  const a = i<10 ? "0"+(i+"") : i+""
  if(i<3){for (let j = 1; j < 32; j++) {
    const b = j<10 ? "0"+(j+"") : j+""
    const num = Number(a+b);
    if (bloomArr[num] !== 0) {
      if (choose.length === 0) {
        choose = [num, bloomArr[num]];
      } else if (choose[1] < bloomArr[num]) {
        choose = [num, bloomArr[num]];
      }
    }
  }}else{
    const b = "01"
    const num = Number(a+b);
    if (bloomArr[num] !== 0) {
      if (choose.length === 0) {
        choose = [num, bloomArr[num]];
      } else if (choose[1] < bloomArr[num]) {
        choose = [num, bloomArr[num]];
      }
    }
  }
}
flowerArr.push(choose);
while (true) {
  const [str, end] = [...choose];
  choose = [];
  if (end > 1130) {
    console.log(flowerArr.length);
    break;
  }
  for (let i = Number(str)+1; i <= Number(end); i++) {
    if (bloomArr[i] !== 0) {
      if (choose.length === 0) {
        choose = [i, bloomArr[i]];
      } else if (choose[1] < bloomArr[i]) {
        choose = [i, bloomArr[i]];
      }
    }
  }
  if (choose.length !== 0) {
    flowerArr.push(choose);
  } else {
    console.log(0);
    break;
  }
}

그리디 문제는 bfs와 dp와 다르게 한눈에 그리디 문제임을 알아차리기가 조금 어려운 것 같다.

그리디 문제 많이 풀어보자!