백준 4408번 파이썬 문제풀이(자기 방으로 돌아가기)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8 

SW Expert Academy

 

---

이 문제 너무 어렵게 생각해서 3시간을 넘게 생각했는데 풀리질 않았다. 힌트를 보니 정말 쉽게 접근할 수 있었다.

간단히 총 복도 길이 리스트 만들고 지나간 길을 +1씩 해주면 된다.. 그 후 가장 많이 지나간 복도(최대값) 출력하면 된다. (심지어 중간에 이 풀이 방식도 생각을 했으나 +1씩 한것이 과연 문제에 해결할 수 있을까? 라고 생각을 하고 지나쳤는데 그게 답이었다.. )

 

조금 생각해야 할점은 홀수 일때와 더 큰방에서 작은방을 갈때이다. 홀수일때는 어차피 +1 값과 똑같이 취급된다. 1번방이나 2번방이나 똑같다는 것이다. 또한 더큰방에서 작은방을 갈때는 작은방에서 큰방으로 가나 반대로가나 똑같기 때문에 애초에 리스트에 담을때 a, b = b , a 로 바꿔주고 담으면 된다.

 

import sys

sys.stdin = open('input.txt', 'r')


def my_max(array):
    max_ = array[0]
    for i in array:
        if max_ < i:
            max_ = i
    return max_


T = int(input())
for order in range(1, T + 1):

    N = int(input())
    array = []
    for i in range(N):
        a, b = map(int, input().split())
        if a % 2:  # 홀수라면
            a += 1  # (1,2),(3,4)...가 똑같기 때문에 +1 해준다.
        if b % 2:  # 홀수라면
            b += 1  # (1,2),(3,4)...가 똑같기 때문에 +1 해준다.
        if a > b:  # 만약 더 큰방에서 작은방으로 갈 경우 a,b를 다시 바꿔준다.
            a, b = b, a
        array.append([a, b])

    hallway = [0] * 401  # 복도를 만든다.
    count = 0
    for i in range(N):  # 입력받은 N을 돌면서
        for j in range(array[i][0], array[i][1] + 1):  # 출발 방부터 도착방까지 이동 동선을 기록
            hallway[j] += 1

    print(f'#{order} {my_max(hallway)}')