4408. 자기 방으로 돌아가기

문제 출처 : SW Expert Academy

문제

복도 구간이 겹치치지 않게 + 이동하는 데에는 거리에 관계없이 단위 시간이 걸린다고 하자.

각 학생들의 현재 방 위치와 돌아가야 할 방의 위치의 목록이 주어질 때, 최소 몇 단위시간만에 모든 학생들이 이동할 수 있는지를 구하시오.

코드

import sys
sys.stdin = open('input.txt')

T = int(input())
for tc in range(1, T+1):
    # 돌아가야 할 학생 수
    N = int(input())
    # 현재방 돌아갈 방
    rooms = [list(map(int, input().split())) for _ in range(N)]
    #
    road = [0] * 201
    for n in range(N):
        # 방번호를 복도 번호로 바꿔주기
        rooms[n][0] = (rooms[n][0]+1) // 2
        rooms[n][1] = (rooms[n][1]+1) // 2

    for i in range(N):
        # 돌아갈 방번호가 더 작은 경우
        if rooms[i][0] > rooms[i][1]:
            rooms[i][0], rooms[i][1] = rooms[i][1], rooms[i][0]
        # 복도 들리는 곳 체크해서 젤 큰수 뽑아내면 그게 답이다!
        for j in range(rooms[i][0], rooms[i][1]+1):
            road[j] += 1

    print("#{} {}".format(tc, max(road)))

어려웠던 점

1. 아예 어떻게 접근을 해야하는지 몰랐다.
2. 복도를 지나는 걸 카운팅해서 그중 젤 큰 수가 답이 되는....
   이 아이디어를 생각해내지 못하고 결국 ... 도움을 받았다.
3. 돌아갈 방번호가 더 작은 경우도 고려하지 못했다.