[백준][9048][Python 파이썬][S3] 수위 아저씨의 고민

 

문제

A 씨는 어떤 회사 빌딩의 수위로 일하고 있다. A 씨는 밤 12 시가 되면 이 빌딩 사무실의 켜져 있는 모든 등과 건물 옥상에 있는 전광판을 소등한 후 퇴근한다. 그런데 이 빌딩은 특이한 구조로 이루어져 있다. 각 층에는 동일한 개수의 사무실이 일렬로 늘어서 있고, 건물 양편에 엘리베이터가 있다. 왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다. 전광판을 끄기 전에는 왼쪽에 있는 엘리베이터만 탈 수 있고, 끈 이후에는 오른쪽에 있는 엘리베이터만 탈 수 있다.

사무실 등은 왼쪽 엘리베이터를 타고 올라가면서 들러 소등할 수도 있고, 오른쪽 엘리베이터를 타고 내려오면서 들러 소등할 수도 있다. A 씨는 왼쪽 엘리베이터 1 층에서 출발하여, 소등하기 위해 이동해야 하는 거리를 최대한 줄이고 싶다. 수위실에서 올려다보면 창문을 통해 소등되지 않은 사무실을 한 눈에 알 수 있으므로, 소등을 시작하기 전에 이 정보를 가지고 소등 경로를 계획하려고 한다.

A 씨가 전광판과 사무실의 등을 끄기 위해 필요한 최소 이동 거리를 계산하는 프로그램을 작성하라. 단, 엘리베이터와 가장자리에 있는 사무실과의 거리나 각 인접한 사무실과의 거리를 1 로 가정한다. 또한 엘리베이터를 이용한 층간 이동 거리도 1 로 가정한다. 

입력

입력은 표준입력(standard input)으로 주어진다. 입력의 첫 번째 줄에는 테스트케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다.

각 테스트케이스 별 입력은 다음과 같이 구성된다.

• 1 번째 줄: 빌딩의 높이(옥상을 제외한 층의 수) F (1 ≤ F ≤ 30), 한 층에 있는 사무실의 수 R (1 ≤ R ≤ 30)와 등이 켜져 있는 사무실의 수 N (0 ≤ N ≤ F×R) 이 입력된다.
• 2~N 번째 줄: 각 줄에 등이 켜져 있는 한 개의 사무실 위치가 입력된다. 사무실 위치는 층 번호 a (1 ≤ a ≤ F) 와 호수 b (1 ≤ b ≤ R) 로 두 개의 정수가 주어지며 빈 칸 하나로 구분된다. (사무실 호수는 왼쪽부터 차례로 1, 2, … , R 로 메겨진다.)

입력에는 같은 방(같은 층, 호수)이 두 개 이상 주어지지 않는다고 가정해도 좋다. 

출력

출력은 표준입력(standard output)으로 출력한다. 각 테스트케이스에 대하여, 소등하기 위해 이동해야 하는 최소 거리를 한 줄에 하나씩 출력한다. 

 

테스트케이스

1 4 5 2 1 1 4 5	1 3 4 8 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4	1 3 4 2 2 2 2 1	1 5 4 2 4 3 3 3
18	27	15	23

 

코드

import sys

input = sys.stdin.readline

for TC in range(int(input())):

    F, R, N = map(int, input().split())

    office = [[0] for i in range(F)]

    for i in range(N):

        r, c = map(int, input().split())

        office[r-1].append(c)

    ans = 2*F + R + 1

    for i in range(F):

        temp = 100000

        office[i] += [R+1]

        office[i].sort()

        for j in range(len(office[i])-1):

            temp = min(temp, office[i][j] + R + 1 - office[i][j+1])

        ans += temp*2

    print(ans)

 

후기

나는바보다 나는바보다 나는바보다 나는바보다  나는바보다 나는바보다  나는바보다 나는바보다  나는바보다 나는바보다 

정렬 안해서 이걸 진짜 얼마나 틀린건지...

제발 여러분들은 저처럼 정렬 안해서 고생하지 말고 편하게 푸세요.. 여기에 몇시간을 쓴거야..

ㅜㅜ