[백준 node.js] 1449번_수리공 항승

백준 그리디 알고리즘 1449번_수리공 항승

난이도 : 실버III

 

문제 설명

입출력

또다른 입출력 예시:

3 3

4 5 9

답 : 2

 

7 4

1 2 3 4 10 15 20

답 : 4

 

문제 풀이 : 좌우 0.5 간격때문에 무지 헷갈렸다. 하지만 그냥 테이프의 길이(L) -1 이라고 생각하면 훨씬 편하다.

구멍난 위치를 기준으로 테이프를 붙이면 구멍난 위치 + 테이프의 길이 -1 만큼이 테이프가 붙여진 길이가 된다.(이를 fix범위라고 지칭) 즉, 테이프가 붙여진 길이안에 포함되어있는 구멍들은 자동으로 수리가 된 셈이다.

이 방식을 이용해서 풀면된다.

 

우선 구멍난 위치를 순차적으로 해결하기 위해 정렬을 해준다.

이 후, 반복문을 통해 fix범위보다 큰 경우(테이프의 범위를 벗어난 경우) 새 테이프를 추가하여 붙인뒤,

fix 범위를 다시 재설정해주면된다.

 

//실버3 수리공 항승
function solution(N, L, list) {
    //구멍난 위치순으로 정렬
    list.sort(function(a,b){
        return a-b;
    })

    //구멍난 위치부터 테이프로 고칠수있는 범위
    let fix = 0;
    let cnt = 0;
    for(let i=0; i<N; i++){
        // fix보다 작거나 같은 구멍난 위치는 하나의 테이프로 해결가능
        if(fix < list[i]){
            //하나의 테이프로 고칠수 있는 범위로 넘어가면
            //새 테이프가 필요하다.
            cnt += 1;
            fix = list[i] + L -1;

        }
    }
    console.log(cnt);
}

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
   //여러줄 입력
   input.push(line)
}).on("close", function () {

    let tmp = input[0].split(" ").map((el) => parseInt(el));
    let N = tmp[0]; //구멍난 개수
    let L = tmp[1]  //테이프 길이
    let list = input[1].split(' ').map((el) => parseInt(el));
    solution(N, L, list);
    process.exit();
});