이성주

현재를 즐기며 미래를 만드는 개발자, 이성주입니다.

    가희와 함께 하는 코딩테스트 4회 풀이
A   [BOJ 25238] 가희와 방어율 무시
B   [BOJ 25239] 가희와 카오스 파풀라투스
C   [BOJ 25240] 가희와 파일 탐색기 2
D   [BOJ 25243] 가희와 중부내륙선

1. 문제

$25243$. 가희와 중부내륙선 (가희와 함께 하는 코딩테스트 4회 D번)

백준 25243번 - 가희와 중부내륙선 (https://www.acmicpc.net/problem/25243)

2. 풀이

  1. 시간의 흐름에 따라서 일을 처리해야 한다.
  2. 시각이 동일하다면, 다른 조건에 의해 일의 우선순위가 결정된다.
  3. 일 처리 후, 해당 일이 사라질 수도 자료구조에 그대로 남아있을 수도 있다.
  4. (1) 조건에 의해서, 일의 시각 정보가 변경되면 해당 일의 자료구조에서의 순위가 바뀌어야 한다.

위 네 가지 조건으로 보아, Priority Queue(우선순위 큐)를 자료구조로 선택하는 것이 바람직하다. 이를 아래와 같이 선언하였다.

struct Train {
    int cur_time;       // 열차가 다음 행동을 취할 시각
    int cur_section;    // 열차가 현재 위치한 구간
    int start_time;     // 열차가 출발한 시각
    int num;            // 열차 index
}

priority_queue<Train, vector<Train>, compare> trains;
// compare는 하위 정렬 기준 (cur_time 비교 -> start_time 비교 -> num 비교)

특정 구간에 열차가 도착했을 때 다른 열차가 그 구간을 사용하고 있다면, 열차가 언제까지 기다려야 하는지를 알아낼 수 있는 방법이 있어야 한다. 따라서, 다음과 같은 vector를 하나 선언한다.

vector<int> section_end_time(4, -1);
// 각 구간별로 그 구간을 사용 가능한 시작 시각의 정보를 담은 vector

그러면, 다음과 같이 설정할 수 있다.

if (section_end_time[train.cur_section] <= train.cur_time) {
    // 열차가 해당 section을 이용한다.
}
else {
    // 열차가 해당 section의 section_end_time까지 기다린다.
}

열차가 해당 section을 이용하면, 다음과 같은 정보들이 변한다.

  1. train.cur_time이 해당 section의 소요 시간만큼 증가
  2. 해당 section의 section_end_time이 (1)에서 변화한 train.cur_time이 됨
  3. train.cur_time이 1 증가 (역에서 멈춘 시간 더해주기)
  4. 하행 또는 상행 종류에 맞춰서 train.cur_section을 $+1$ 또는 $-1$

열차가 해당 section을 이용하지 못하면, 다음과 같은 정보들이 변한다.

  1. train.cur_time이 해당 section의 section_end_time이 됨

하행 또는 상행 종류에 맞춰서 열차가 종착역에 도착하면 해당 NODE를 pop하고, 그렇지 않으면 정보만 변화시키면서 우선순위 큐를 돌린다.

최종 갱신된 train.cur_time과 train.num으로 적절히 정렬하여 정답을 출력할 수 있다.

3. 채점 결과

boj-25243

4. 회고

우선순위 큐를 사용하면 좋다는 사실만 알아채면, 어렵지 않게 풀 수 있었던 문제였다.

5. 코드

댓글남기기