SW Expert Academy 4408 자기 방으로 돌아가기 - C++

아주 간단한 설명의 문제이다.

추억의 상황설정도 있고

문제 자체도 흥미롭다.

 

우선, 건너편 방으로 건너갈 때를 생각해보자.

 

만약 1번 학생이 400번 방에 들어간다면 

1 ~ 400 번에 해당하는 동선이 막혀버린다.

만약 398 번에 들어간다면

1 ~ 398 번에 해당하는 동선이 막힌다.

...

만약 2번에 들어간다면

1 ~ 2번에 해당하는 동선이 막힌다.

 

만약 2번 학생이 399번 방에 들어간다면

1 ~ 400번에 해당하는 동선이 막힌다.

397번 방에 들어간다면 1 ~ 398번 동선이 막힌다.

...

1번 방에 들어간다면 1 ~ 2번 동선이 막힌다.

 

그럼, 같은 편 방으로 건너갈 때를 생각해보자.

 

만약 1번 학생이 399번으로 들어간다면

1 ~ 400번 동선이 막힌다.

397번으로 들어간다면 1 ~ 398,

...

3번으로 들어간다면 1~4 가 막힌다.

 

2번학생이 400번에 들어간다면

1 ~ 400번 동선이 막힌다.

398번으로 들어간다면 1~398,

...

4번으로 들어간다면 1~4 가 막힌다.

 

즉, 시작번호 < 도착번호인 경우 이동하는 경우가 총 4가지 있는데,

 

1. 홀수 -> 짝수 = [홀수, 짝수] 동선이 막힌다.

2. 홀수 -> 홀수 = [홀수, 홀수) = [홀수, 홀수+1] 동선이 막힌다.

3. 짝수 -> 짝수 = [짝수-1, 짝수] 동선이 막힌다.

4. 짝수 -> 홀수 = [짝수-1, 홀수) = [짝수-1, 홀수+1] 동선이 막힌다.

• 단, [a, b] 는 닫힌 구간으로 {a, a+1, ..., b-1, b}를 뜻하고
  (a,b) 는 열린 구간으로 {a+1, a+2, ..., b-2, b-1}를 뜻한다.

시작점이 짝수인 경우 1 작은 홀수로 생각하고,

도착점이 홀수인 경우 1 큰 짝수로 생각할 수 있으므로, 

이를 이용하여 방번호 (1,2), (3,4), (5,6), ..., (399, 400) 을 묶어서 하나의 동선으로 여길 수 있다.

 

출발점 1, 2는 동선 1로

출발점 3, 4 는 동선 2로

...

(399, 400) 은 동선 200

 

이를 일반적으로 표현하면 아래와 같다.

• (출발점 동선, 도착점 동선) = (출발점 / 2 + 출발점 % 2, 도착점 / 2 + 도착점 % 2)  

 

추가적으로, 

학생들이 누가 먼저 이동하던 순서는 상관 없다.

 

왜냐하면 해당 학생이 지나갈 때는 어차피 동선이 막히기 때문에

동시에 이용할 수 있는 학생의 수는 정해져 있고,

동선이 겹치는 경우는 다른 시간에 항상 가야 하기 때문입니다.

 

즉 a, b, c, d, e, f 중에 c, d, e 는 다르게 이동해야하고, a, f 가 다르게 이동해야한다면

c

d

e

는 항상 다르게 배치되어야 하고, a, f 는 사이에 아무데나 끼어넣으면 된다.

이 말 뜻은 가장 긴 exclusive set 가 항상 정답으로 나온다는 뜻이므로,

겹칠 수 없는 가장 긴 배치를 구하는 것과 마찬가지이므로

최대한 같이 다닐 수 있는 동선은 최대한 같이 넣을 수 있을만큼 넣으면 된다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SWAP(x,y) {int tmp=x; x=y; y=tmp;}
 
int t, n, s, e;
typedef struct st {
    int s, e;
}ST;
 
ST student[400 * 400+1];
int* used;
 
 //정렬에 쓰이는 비교함수
int comp(const void* p, const void* q) {
    ST* a = (ST *)p, * b = (ST*)q;
    return a->s - b->s;
}
 
int solve() {
//정렬해서 최대한 많은 수의 동선을 넣을 수 있도록
    qsort(student, n, sizeof(ST), comp);
    int ret = 0;
    int flag = 0;
    int end = 0;
     //더이상 배치할 동선이 없을 때까지 반복한다.
    while (1) {
        flag = 0;
        end = 0;
        //n명의 학생을 순회한다.
        for (int i = 0; i < n; i++) {
            //이미 돌아간 학생이라면 무시
            if (used[i]) continue;
            //동선 시작점이 마지막으로 선택된 동선 도착점이랑 겹치지 않으면 학생 이동
            if (student[i].s/2 + student[i].s%2 > end) {
                used[i] = 1;
                end = student[i].e/2 + student[i].e%2;
                //동선에 배치했다.
                flag = 1;
            }
        }
        //학생 없으면 끝
        if (flag==0) break;
        ret++;
    }
    return ret;
}
 
int main() {
    scanf("%d", &t);
    for (int loop = 1; loop <= t; loop++) {
        scanf("%d", &n);
        used = (int*)calloc(n, sizeof(int));
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &student[i].s, &student[i].e);
            //항상 시작점 < 도착점이 되도록
            if (student[i].s > student[i].e) SWAP(student[i].s, student[i].e);
        }
        printf("#%d %d\n", loop, solve());
        free(used);
 
    }
}