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

문제

고등학교 학생들이 학교에서 수련회를 갔다. 수련회에 간 학생들은 친구들과 음주가무를 즐기다가 밤 12시가 되자 조교들의 눈을 피해 자기방으로 돌아가려고 한다.
제 시간에 자기방으로 돌아가지 못한 학생이 한 명이라도 발견되면 큰일나기 때문에 최단 시간에 모든 학생이 자신의 방으로 돌아가려고 한다.
숙소는 긴 복도를 따라 총 400개의 방이 다음과 같이 배열되어 있다.

모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.
예를 들어 (방1 -> 4) 와 (방3 -> 6) 은 복도 구간이 겹치므로 한 사람은 기다렸다가 다음 차례에 이동해야 한다. 이동하는 데에는 거리에 관계없이 단위 시간이 걸린다고 하자.
각 학생들의 현재 방 위치와 돌아가야 할 방의 위치의 목록이 주어질 때, 최소 몇 단위시간만에 모든 학생들이 이동할 수 있는지를 구하시오.

입력
입력은 T(≤10)개의 테스트 케이스로 되어 있다. 각 테스트 케이스의 첫 줄에는 돌아가야 할 학생들의 수 N이 주어진다.
다음 N 줄에는 각 학생의 현재 방 번호(≤400)와 돌아가야 할 방의 번호(≤400)가 주어진다. 주어지는 2N개의 방 번호 중 중복되는 것은 없다.

출력
테스트 케이스 T에 대한 결과는 “#T ”을 찍고, 각 테스트 케이스마다 필요한 시간을 한 줄에 하나씩 출력한다.

 

내가 쓴 코드

T = int(input())
for t in range(T):
    N = int(input())
    corridor = [0] * 401    # 각 번호의 복도 지나는 횟수 저장
    move = 0    # corridor의 최대값
    for _ in range(N):
        cur, togo = map(int, input().split())
        # cur -> togo 방향(왼->오) 통일화
        if cur > togo:
            cur, togo = togo, cur
        # cur, togo 모두 홀수로 맞추기(윗방으로 이주)
        if cur % 2 == 0:
            cur -= 1
        if togo % 2 == 0:
            togo -= 1
        # 지나는 복도 모두 +1 check
        for cor in range(cur, togo + 1):
            corridor[cor] += 1
        # corridor 지나는 횟수 최댓값 구하기
            if corridor[cor] > move:
                move = corridor[cor]

    print(f'#{t+1} {move}')

오늘 수업 때 전략을 설명해주셔서 그 전략을 활용하여 풀 수 있었다. 아무도 알려주지 않았다면, 혼자 풀기 힘들었을 것 같다. 다 구해놓고 마지막 답을 어떻게 구해야 하는지 헤메고 있었다. 복도 지나는 횟수의 최댓값이 정답이었다. 항상 답은 간단하게 풀면 나오는 것 같은데, 난 어렵게만 생각하고 있지....ㅜㅜ

 

출력 결과

#1 1

#2 2

#3 3