[SWEA] #4408 자기 방으로 돌아가기.python(파이썬)

문제 링크 / 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8&categoryId=AWNcJ2sapZMDFAV8&categoryType=CODE&problemTitle=4408&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제요약

학생들이 자기 방으로 돌아갈 때, 서로 복도의 구간이 겹치지 않게 하면서 돌아갈 수 있는 최소 시간을 구하는 문제

[제약 사항]

• 두 학생이 돌아가면서 지나는 복도의 구간이 겹치면 동시에 돌아갈 수 없다.
• 방의 번호 ≤ 400
• 학생들의 수 N
• 주어지는 2N개의 방 번호 중 중복되는 것은 없다.
• 이동하는 데에는 거리에 관계없이 단위 시간이 걸린다

 

풀이

구간이 겹치면 동시에 돌아갈 수 없고, 거리에 관계없이 단위시간이 걸리므로 최소 단위 시간은

 

특정복도구간에서 학생들이 지나간 횟수와 같다.

 

1. 방번호가 1부터 시작하고 양쪽에 하나씩 있으므로, 복도 1칸당 방 2개씩 묶어 번호를 부여해주기 위하여 lambda식을 사용했다.
2. 출발방과 도착방이 서로 바뀌어도 경로는 동일하므로 두 방의 복도번호 중 작은 값을 경로 시작점으로, 큰값을 경로 도착점으로 하였다.
3. for문을 순회하며 복도번호별 지나간 횟수를 카운트.
4. 최대 카운트를 구하여 문제를 풀이했다.

 

코드

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    rooms = [list(map(lambda x:(int(x)-1)//2, input().split())) for _ in range(N)]  
    # 방이 양쪽에 하나씩 있으므로 짝을 맞춰 복도번호를 부여해주기위해,
    # lambda를 활용하여 각 방번호에 1을 뺀 후 2로 나눈 몫을 구함

    corridor = [0] * 200    # 방번호가 최대 400이므로 복도번호 최대 200
    for start_corr_num, end_corr_num in rooms:
        if start_corr_num > end_corr_num:   # 시작방번호가 더 클경우 서로 바꿔줌
            num1, num2 = end_corr_num, start_corr_num
        else:
            num1, num2 = start_corr_num, end_corr_num

        for corr_num in range(num1, num2+1):
            corridor[corr_num] += 1     # 복도를 한번 지나갈 때 마다 1씩 추가

    # 복도번호 중 최대 cnt구하기
    max_cnt = 0
    for cnt in corridor:
        if max_cnt < cnt:
            max_cnt = cnt

    print('#{} {}'.format(tc, max_cnt))