[BOJ #2594] 놀이공원

오늘의 문제는 2005년도 KOI 시.도 지역본선 2번인 [놀이공원]이에요.

#1931 회의실배정과 비슷하게 시작시간만을 보며 정렬한 뒤(회의실배정은 종료시간으로 정렬하죠 ㅎㅎ) 앞에서부터 탐색하며 풀이해도 풀리지만, 그러한 풀이는 이미 친절하게 포스팅 되어있어서, 저는 다른 방식으로 풀이해보았어요.

라인 스위핑의 기초 중의 기초 형태인데

#10714 JOI 2015년도 1번 기차여행 역시 본 풀이에서 사용한 기법을 이용하여 간단히 풀려요.

---

[Baekjoon Onine Judge]

#2594 놀이공원

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

2005 한국정보올림피아드 시.도지역본선 고등부 2번

---

Problem Solving Strategy

하나라도  놀이기구가 운행 중이면, 철수와 영희는 데이트를 하지 못합니다.

반대로 말해, 우리가 확인해야하는 것은 '모든 놀이기구가 정지해있는가'에 대한 여부만 확인하면 됩니다.

지금 특정한 어느 놀이기구가 운행중인지는 궁금하지 않습니다.

문제 해결 아이디어는 간단합니다.

어떤 놀이기구의 운행 시작시간은 종료시간보다 반드시 앞서지요.

시간 순서대로 탐색하며 어떤 놀이기구의 운행이 시작할 때 +1을 하고 종료할 때 -1을 계산해주면, 그 순간에 몇 대의 놀이기구가 운영중인지를 알 수 있으며, 변수가 0이 될 경우에는 모든 놀이기구가 정지한 것입니다.

일단 입력을 꼼꼼하게 받아봅시다.

1.입력은 분 단위로 받아줍니다.

분 단위 출력만 하면 되므로 이 편이 뒤에서 변수를 다룰 때 코딩이 편하므로 당연하겠지요.

운행 10분전부터 10분 후까지도 철수와 영희는 만나지 못하므로, 해당 시간 역시 고려하여 받아줍시다.

for(int i=0;i<N;i++){
    scanf("%d %d",&input_start,&input_finish);
    start[i]=(input_start/100)*60+(input_start%100)-10;
    finish[i]=(input_finish/100)*60+(input_finish%100)+10;
}

2. 시작시간과 종료시간을 각각 오름차순으로 정렬합니다.

정렬하며 어느 놀이기구의 시작시간과 종료시간을 매칭시킬 정보는 잃지만, 저희는 단지 어느 순간에 놀이기구가 시작하거나 종료했는지만 궁금하므로, 편하게 따로 정렬합시다.

sort(start,start+N);
sort(finish,finish+N);

3. 시간 순서대로 탐색하며 시작과 종료의 개수를 카운팅합니다.

시간 순서대로 탐색하며 어떤 놀이기구의 운행이 시작할 때 +1을 하고 종료할 때 -1을 계산해주면, 그 순간에 몇 대의 놀이기구가 운영중인지를 알 수 있으며, 변수가 0이 될 경우에는 모든 놀이기구가 정지한 것입니다.

위에서 언급했던 대로입니다.

합병 정렬 (merge sort) 코드를 짤 때 처럼 start(시작 시간을 저장한 배열)과 finish(종료 시간을 저장한 배열)을 시간순으로 쭈욱 훑으며 코딩합니다.

int s=0,f=0,MAX=0,active=0,start_break=600;
for(int i=0;i<(N*2);i++){
    if(start[s]<finish[f] && s!=N){//어떤 놀이기구의 운행이 시작함 
        active++;
        if(active==1 && MAX<(start[s]-start_break)){
            MAX=start[s]-start_break;
        }
        s++;
    }
    else{//어떤 놀이기구의 운행이 끝남
        active--;
        if(active==0){
            start_break=finish[f];
        } 
        f++;
    }
} 

---

틀리기 쉬운 부분

저는 22시를 분으로 변환하다가 13200이라 계산해서 제출 횟수를 상당히 낭비했지만... ㅋ...

코딩만 꼼꼼히 한다면 거의 없습니다.

4. 극단 값을 계산할 때 음수가 발생하지 않을까

입력을 받을 때 편하게 무차별적으로 10을 가감하고 받았는데 걱정할 법도 하지만 3번 질문의 코드처럼 MAX를 0이로 선언하고 항상 비교 후 갱신이 일어나도록 하면 걱정하는 일은 잃어나지 않음이 증명됩니다.

마지막으로 하루 일과를 시작하는 시간과 끝내는 시간을 고려하여 코딩을 마무리해줍니다.

---

전체 코드 보기

#include<cstdio>
#include<algorithm>
using namespace std;
int N,start[55],finish[55];
int main(void){
    scanf("%d",&N);
    int input_start,input_finish;
    for(int i=0;i<N;i++){
        scanf("%d %d",&input_start,&input_finish);
        start[i]=(input_start/100)*60+(input_start%100)-10;
        finish[i]=(input_finish/100)*60+(input_finish%100)+10;
    }
    sort(start,start+N);
    sort(finish,finish+N);
    int s=0,f=0,MAX=0,active=0,start_break=600;
    for(int i=0;i<(N*2);i++){
        if(start[s]<finish[f] && s!=N){//어떤 놀이기구의 운행이 시작함 
            active++;
            if(active==1 && MAX<(start[s]-start_break)){
                MAX=start[s]-start_break;
            }
            s++;
        }
        else{//어떤 놀이기구의 운행이 끝남
            active--;
            if(active==0){
                start_break=finish[f];
            } 
            f++;
        }
    } 
    /*마지막 놀이기구의 운행종류부터 일과를 마치는 시각까지*/
    if(MAX<(1320-start_break)){
        MAX=1320-start_break;
    }
    printf("%d",MAX);
}

블로그에 공개를 하기 위해 코드가 많이 얌전해졌는데, 보통 굉장히 지저분하게 코딩을 해왔어서 그 습관이 여기저기 들어 있을 거 같아 피드백은 언제나 환영해요 *^~^*