Problem

24시간 운영되는 물류센터에는 화물을 싣고 내리는 도크가 설치되어 있다.

0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오.

신청서에는 작업 시작 시간과 완료 시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.

예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다.

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 신청서 N이 주어지고, 다음 줄부터 N개의 줄에 걸쳐 화물차의 작업 시작 시간 s와 종료 시간 e가 주어진다.

1<=N<=100, 0<=s<24, 0 ＜ e ＜= 24

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

Solving

아이디어

0~24시 까지의 배열을 만들어서 도크 작업이 진행되는 시간대를 채워나가는 식으로 진행
중복되지 않도록 도크 작업을 하는 화물을 체크
매 탐색마다 가장 짧게 작업하는 화물을 찾아서, 작업하는 시간을 채우고, 체크표시 하고, 카운팅 하고, 다시 탐색한다. 매 탐색마다 가장 짧게 작업하는 경우를 카운팅 하다 보면, 결국 가장 많이 작업할 수 있는 수를 알아낼 수 있다.
탐색에서 작업 가능한 화물을 찾지 못하면, 이 때까지 한 카운팅이 최대 카운팅

코드

def function(cnt):
    global max_cnt
    # 가장 적게 이용하는 화물을 찾을 변수
    min_usage_time = 987654321
    idx = 0
    for i in range(N):
        # 작업에 포함된 화물은 pass
        if checked[i]: continue
        tmp_start, tmp_end = start_end[i]
        # 해당 화물이 차지하는 작업 시간이
        # 이미 다른 화물에 할당되어 있으면 break
        # 즉, 해당 화물은 작업 가능하지 않다면 break
        for t in range(tmp_start, tmp_end):
            if time[t]:
                break
        # 해당 화물이 작업 가능하다면
        else:
            # 남은 화물 중에서 해당 화물이 가장 적게 이용하는 경우라면 갱신
            tmp_time = tmp_end - tmp_start
            if min_usage_time > tmp_time:
                min_usage_time = tmp_time
                idx = i
    # 값이 갱신되지 않았다면, 더이상 작업할 수 있는 화물이 없다는 뜻
    if min_usage_time == 987654321:
        return cnt

    # 값이 갱신되었다면, 해당 화물을 체크하고, 시간을 할당한다.
    checked[idx] = 1
    start, end = start_end[idx]
    for t in range(start, end):
        time[t] = 1
    # 재귀 (남은 화물 가지고 다시 조사)
    return function(cnt + 1)


for tc in range(1, int(input()) + 1):
    N = int(input())
    # [시작시간, 종료시간]
    start_end = [list(map(int, input().split())) for _ in range(N)]

    time = [0] * 25     # 0시 ~ 24시
    checked = [0] * N   # 작업 가능한 화물 체크

    print(f'#{tc} {function(0)}')

저작자표시