[백준] 0925 오늘의 문제 풀이📚

오늘은 그리디 알고리즘을 다뤄봤다.

사실 그리디 알고리즘 문제를 풀면서 느낀건데 그리디 알고리즘으로 문제를 푸는 것 자체보다도,

이 문제가 그리디 문제인지 아닌지를 판별하는 능력이 훨씬 중요한 것 같았다..

 

근데, 뭐 사실 아무 알고리즘 생각 안하고

일단 눈앞에 보이는대로 풀면 그게 그리디인 것 같다.

지금까지 그렇게 풀어왔던 문제들이 대부분 그리디 문제였던 듯?

 

1. 동전 0

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const firstLine = input.shift().split(' ');
    const N = Number(firstLine[0]);
    let K = Number(firstLine[1]);
    const coins = [];

    for(let i = 0; i < N; i++) {
        coins.push(Number(input[i]));
    }
    coins.sort((a, b) => b - a);
    
    let idx = 0;
    let counts = 0;
    while(K > 0) {
        const q = K / coins[idx];
        if(q >= 1) {
            K = K - coins[idx] * (q << 0);
            counts = counts + (q << 0);
        } else {
            idx++;
        }
    }
    console.log(counts);
});

아주 유명한 문제. 학교에서 수업할 때도 들어봤다.

동전 문제로 그리디를 풀 수 있는 건, 동전 금액들 사이에 배수 관계가 성립해야한다고 한다.

만약 그렇지 않다면, 일부의 최적해가 전체의 최적해가 되는 게 아니기 때문.

그냥, 쉽게 말해 예제용 문제인듯.

 

2. 회의실 배정

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const N = Number(input.shift());
    const meetings = [];
    let counts = 1;

    for(let i = 0; i < N; i++) {
        const meet = input[i].split(' ');
        meetings.push([Number(meet[0]), Number(meet[1])]);
    }
    
    meetings.sort((a, b) => a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]);

    let meetingIdx = 0;
    for(let i = 1; i < N; i++) {
        if(meetings[i][0] >= meetings[meetingIdx][1]) {
            counts++;
            meetingIdx = i;
        }
    }

    console.log(counts);
});

일단, 그리디 문제에서는 뭔가 정렬이 중요하다는 느낌을 받았다.

탐색 자체가 그렇지만, 정렬을 하고나면 금방 찾을 수 있는 배열 요소도

정렬을 하지 않으면 빙빙 돌아서 찾아야 하니깐..

 

그리고, 문제를 풀려면 회의가 끝나는 시간을 기준으로만 정렬을 하는 게 아니라

회의가 끝나는 시간이 같다면, 걔네들끼리는 시작 시간을 기준으로 또 정렬을 해줘야 한다.

문제에 다음과 같은 조건이 있기 때문.

'회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.'

 

0번 요소부터 순차적으로 탐색을 한다고 쳤을 때,

시작하자마자 끝나는 회의가 종료 시간이 동일한 다른 회의들보다 앞에 있으면 걔를 카운트할 수 있는데,

종료시간이 동일한 다른 회의들보다 뒤에 있으면 카운트하지 못하고 지나가기 때문.

 

3. 로프

문제 링크

a. 혼자 풀이

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const N = Number(input.shift());
    const ropes = [];

    for(let i = 0; i < N; i++) {
        ropes.push(Number(input[i]));
    }
    ropes.sort((a, b) => a - b);

    let max = 0;

    while(ropes.length > 0) {
        const res = ropes[0] * ropes.length;
        if(res > max) max = res;
        ropes.splice(0, 1);
    }
    console.log(max);
});

 

b. 참고하여 다시 풀이

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const N = Number(input.shift());
    const ropes = [];

    for(let i = 0; i < N; i++) {
        ropes.push(Number(input[i]));
    }
    ropes.sort((a, b) => a - b);

    let max = 0;

    for(let i = 0; i < N; i++) {
        const res = ropes[i] * (N - i);
        if(res > max) max = res;
    }
    console.log(max);
});

그래도 혼자서 잘 풀었다고 생각했는데

웬걸, 시간이 6876ms가 걸렸다. 이게 통과됐다는 게 더 신기할 정도;

그래서 다른 사람이 푼 풀이를 봤더니 세자리수더라.

뒤에 풀이보다 좀 멍청한 풀이긴 해도, 이렇게까지 차이가 많이 날줄은 몰랐다.

생각보다 splice 연산이 시간을 엄청 잡아먹나봄.

 

정렬을 최대한 이용하고

splice같은 특수 연산들은 최대한 안쓰는 방향으로 풀이를 생각해보자.

 

사실, N - i는 생각을 절대 못했을 것 같기도.

별것도 아닌데 왜이렇게 떠올리기가 힘든건지.