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

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

고등학교 학생들이 학교에서 수련회를 갔다. 수련회에 간 학생들은 친구들과 음주가무를 즐기다가 밤 12시가 되자 조교들의 눈을 피해 자기방으로 돌아가려고 한다.

제 시간에 자기방으로 돌아가지 못한 학생이 한 명이라도 발견되면 큰일나기 때문에 최단 시간에 모든 학생이 자신의 방으로 돌아가려고 한다.

숙소는 긴 복도를 따라 총 400개의 방이 다음과 같이 배열되어 있다.

모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.

예를 들어 (방1 -> 4) 와 (방3 -> 6) 은 복도 구간이 겹치므로 한 사람은 기다렸다가 다음 차례에 이동해야 한다. 이동하는 데에는 거리에 관계없이 단위 시간이 걸린다고 하자.

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

입력

입력은 T(≤10)개의 테스트 케이스로 되어 있다. 각 테스트 케이스의 첫 줄에는 돌아가야 할 학생들의 수 N이 주어진다.

다음 N 줄에는 각 학생의 현재 방 번호(≤400)와 돌아가야 할 방의 번호(≤400)가 주어진다. 주어지는 2N개의 방 번호 중 중복되는 것은 없다.

출력

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

예제

입력

3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

출력

#1 1
#2 2
#3 3

My Sol

T = int(input())
for tc in range(T):
    N = int(input())
    matS = [list(map(int, input().split())) for _ in range(N)]
    max_r = 0
    for i in range(N):
        for j in range(2):
            if max_r < matS[i][j]:
                max_r = matS[i][j]

    cor = [0]*(max_r//2+2)

    for i in range(N):
        lst = []
        for j in matS[i]:
            k = (j//2+1) if j%2 else (j//2)
            lst.append(k)
        a, b = lst
        if a > b:
            a,b = b,a
        for r in range(a, b+1):
            cor[r] +=1
    ans = 0
    for v in cor:
        if ans < v:
            ans = v

    print(f'#{tc+1} {ans}')

D4의 난이도를 생각하면 꽤나 쉽게 풀었던 문제였다. counting을 활용하면 쉽게 풀 수 있는 문제였다.

처음에는 방까지 포함해서 3행, 그리고 최대 방의 호수//2를 열로 하는 2차원 배열을 생각했으나, 방은 셀 필요가 없이 복도에 나오는 순간의 열값부터 들어가는 방의 열값까지 인덱스를 하여 하나씩 더해주면 되겠다. 만약 동선이 겹치게 되면 1차원 리스트에 다른 학생들의 동선 위에 1을 덮어씌우므로 필요한 단위시간은 2가 될 것이고, 그 이후에도 3, 4 이렇게 올라갈 것이다. 때문에 인덱스를 계산하여 모두 카운팅해준 뒤, 최댓값을 구하면 이것이 필요한 단위 시간이다.

학생들의 현재 방과 목적지를 입력받아 2차원 배열로 저장한다. 그리고 입력을 모두 받으면 방의 호수의 최댓값을 구한다. 이 값을 2로 나눈 값에 2만큼 추가한 것에 대하여 카운팅 배열 cor을 만들어줄 것이다. 이렇게 함으로써 불필요하게 많은 수의 배열을 만들고 조회할 필요가 없어진다. 뭐 방의 최대치인 400과 그의 결과로 계산되는 202개의 열이더라도 그렇게 많은 차이는 아닐테지만 말이다.

열을 의미하는 j를 2로 나눈 몫만 취하는데, 이때 홀수번호의 방이라면 다음 열로 넘어가게 되므로 홀수라면 열을 하나 더 추가하는 방식을 사용하였다. 그와 동시에 이렇게 두 방의 열을 체크하여 더 큰 수를 뒤로 보냈다. 만약 뒤의 수가 더 작다면 range로 카운팅을 할 때 오류가 발생할 수 있기 때문이다.

그리고 두 방의 열을 모두 포함하도록 종료 인덱스+1을 하고 각 인덱스마다 cor에 해당하는 인덱스에 1을 더하며 카운팅하고 이 과정이 끝나면 최대치를 구한다.

결과

PASS