[JavaScript] 백준 2457번 - 공주님의 정원

[문제]

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

2457번: 공주님의 정원

[풀이]

find()를 통해 가장 적게 꽃을 피울 수 있는 조합을 구해주었는데, find()는 아래와 같은 작업을 반복합니다.

• 아직 방문하지 않은(피우지 않은) 꽃 중에서 현재 조회중인 시작 날짜와 같거나 이전에 피어서 가장 늦게 지는 꽃을 찾아서 해당 꽃의 index를 저장
• 만약 꽃을 찾지 못했다면 조건을 만족하지 못하여 0을 출력하고 종료
• 만약 조회된 index의 종료 날짜가 12월 1일 이후라면 이제까지 핀 꽃의 개수를 출력하고 종료
• index를 방문 처리 하고 꽃의 개수 + 1을 통해 갱신

따라서 예시 1번 코드의 동작 과정을 살펴보면

• index 1의 [ 1, 1, 6, 30 ] 을 고른 후, 조회할 기준 날짜를 6 / 30로 갱신하고 cnt++
• index 3의 [ 6, 10, 12, 10 ] 을 고른 후, 종료 날짜가 12 / 10로 12월 1일 이후의 날짜이기 때문에 종료하고 cnt++을 출력

[코드]

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split('\n');

const N = parseInt(input[0]);

const arr = [];

for(let i=1;i<=N;i++) {
    arr.push(input[i].split(" ").map(Number));
}

// 기준 날짜 m, d를 넘지 않고 가장 오래 지속되는 꽃을 고름

let cnt = 0;

const find = () => {
    let m = 3;
    let d = 1;
    let index = -1;
    
    let endMonth = 0;
    let endDay = 0;

    const visit = Array(N).fill(false);

    while(true) {
        for(let i=0;i<N;i++) {
            if(visit[i]) {
                continue;
            }
            if(arr[i][0] < m || (arr[i][0] === m && arr[i][1] <= d)) {
                if(arr[i][2] > endMonth || (arr[i][2] === endMonth && arr[i][3] > endDay)) {
                    index = i;
                    endMonth = arr[i][2];
                    endDay = arr[i][3];
                }
            }
        }
        if(index == -1) {
            console.log(0);
            break;
        }
        m = arr[index][2];
        if(m === 12) {
            console.log(cnt + 1);
            break;
        }
        d = arr[index][3];
        visit[index] = true;
        cnt++;
        endMonth = 0;
        endDay = 0;
        index = -1;
    }
}

find();