소가 길을 건너간 이유( BOJ 14469 )

문제 : https://www.acmicpc.net/problem/14469

14469번: 소가 길을 건너간 이유 3

 

문제 파악하기

N마리의 소가 농장에 도착해서 검문을 완료하기까지 걸리는 최소 시간을 구하는 문제입니다. N마리 소에 대한 2가지 정보(도착 시간, 검문시간)를 이해하면 문제는 어렵지 않게 해결할 수 있습니다.

 

문제 해결하기

우선 도착 시간은 소가 검문을 할 수 있는 시간을 의미합니다. 따라서, 우리는 소들을 도착한 시간을 기준으로 정렬하면 대략적인 순서를 정할 수 있습니다. 그럼 검문 시간은 어떨까요? 단순히 생각해보면 검문 시간이 짧은 소부터 입장을 해야할 듯 합니다. 그래야 가장 효율적으로 입장할 수 있을 것 같기 때문입니다. 사실 틀린 말은 아니지만 우리는 이 문제에서 어떤 결괏값을 요구하는지 확인할 필요가 있습니다. 이 문제에서는 소들의 검문이 모두 완료되는 최소 시간을 구하길 원합니다. 소들이 얼마나 기다리는지 상관없기에 우리는 도착한 소들을 단순히 순서대로 입장시키면서 검문이 완료되는 시간을 체크하면 정답을 구할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define PAIR pair<int, int>
using namespace std;
 
int N, a, b, ret;
vector< PAIR > inp;
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d %d", &a, &b);
        inp.push_back({a, b});
    }
 
    // sort
    sort(inp.begin(), inp.end());
 
    // sv
    ret = 0;
    for(int i=0;i<N;i++) {
        if(ret <= inp[i].first) ret = inp[i].first + inp[i].second;
        else ret += inp[i].second;
    }
 
    // print
    printf("%d", ret);
}

후기

운영체제의 SJF 알고리즘이 떠오르는 문제였습니다. 다만 이 문제에서는 소들의 대기시간을 신경쓰지 않기에 단순히 정렬하기만 하면 되었지만 소들의 대기시간을 각각 생각해야 한다면 좀 더 재미있는 문제가 될 수 있다고 생각합니다. 정렬을 소개하는 좋은 문제라고 생각합니다.