터보모드(TURBOMODE) 정답 코드

난이도 ★☆☆☆☆

문제

N(1~1000)개의 Process 를 돌릴 수 있으며, 동시에 최대 100개의 Process 를 실행할 수 있다.

 

1~1000초 사이 동안 5개의 Process 가 실행되는 시간이 아래 그림과 같다면

 

2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	…	996	997	998	999	1000

 

Turbo mode 로 실행되는 Process의 개수를 출력하시오. (단, Turbo mode 는 Process 가 연속으로 3초 이상 실행되면 동작하며, 입력은 Process 의 시작 시간을 기준으로 오름차순으로 주어진다)

 

입력

5  → 입력할 Process 의 개수

1 3

4 6

6 8

12 16

13 15

출력

2

힌트

Greedy로 Process를 한번씩만 탐색하면 끝난다. O(n)  → ① Process 하나를 먼저 입력받고 시작시간과 종료시간을 저장한다.  → ② Process를 하나씩 입력받으면서, 시작시간이 기존 Process의 종료시간보다 이르면 합치고  → ③ 늦으면 기존 Process를 새걸로 덮어쓴다. 이때 기존 Process의 지속시간이 3초 보다 길었다면 count++ 해준다.

이하는 코드입니다.

#include <stdio.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
typedef struct {
    int start;
    int end;
} P;    // Process
 
int main() {
    int sizeOfP;
    scanf("%d\n", &sizeOfP);
 
    int count = 0;
 
    P oldP;
    scanf("%d %d", &oldP.start, &oldP.end);
    sizeOfP--;
 
    while (sizeOfP-- > 0) {
        P newP;
        scanf("%d %d", &newP.start, &newP.end);
 
        if (newP.start <= oldP.end) {
            oldP.end = MAX(oldP.end, newP.end);
        }
        else {
            if ((oldP.end - oldP.start) >= 3) {
                count++;
            }
            oldP.start = newP.start;
            oldP.end = newP.end;
        }
    }
 
    if ((oldP.end - oldP.start) >= 3) {
        count++;
    }
 
    printf("%d\n", count);
 
    return 0;
}