[SWEA] 자기 방으로 돌아가기

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

상당히 어려운 문제이다. 아이디어를 생각하는게 어려웠다...

풀이

방은 기본적으로 홀수 방은 위쪽에, 짝수 방은 아래쪽에 배치되어있다. 같은 열에 있는 두 방은 동일 선상으로이라고 볼 수 있으므로 400개의 방을 200개의 방으로 줄여서 생각할 수 있다.

예를 들어, 1번 방에 있던 학생은 4번 방으로, 5번 방에 있던 학생은 6번 방으로 이동해야하는 상황이라고 해보자. 

8개였던 방을 4개의 방으로 줄여서 표현해보면 아래의 그림과 같다고 할 수 있다.

그렇다면 이제 배열을 만들어 각 학생들을 옮겨보자.

for (int j = a; j <= b; j++) room[j]++;

a방에서 b방으로 이동하는 학생의 이동경로를 배열에 표현한 것이다.
이렇게 하면 모든 학생이 이동하였을 때 room[i]의 값 중에서 가장 큰 값이 정답이 된다. 왜냐하면 경로가 겹치는 학생들의 숫자이므로 모두 다 다른 시간에 움직여야하기 때문이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int room[201];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    for (int c = 1; c <= t; c++) {
        int n;
        cin >> n;
        fill(room, room + 201, 0);
        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            if (a > b) swap(a, b);
            // 방 번호를 1/2로 줄여준다
            if (a % 2 == 1) a++;
            if (b % 2 == 1) b++;
            a /= 2;
            b /= 2;
            // 방 이동 표현
            for (int j = a; j <= b; j++)
                room[j]++;
        }
        int ans = 0;
        for (int i = 0; i <= 200; i++)
            ans = max(ans, room[i]);
        cout << "#" << c << ' ' << ans << '\n';
    }
}