[SWEA][D3][#11805] 탐욕_화물 도크

출처

• SW Expert Academy

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

문제

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
5
20 23
17 20
23 24
4 14
8 18
10
14 23
2 19
1 22
12 24
21 23
6 15
20 24
1 4
6 15
15 16
15
18 19
2 7
11 15
13 16
23 24
2 14
13 22
20 23
13 19
7 15
5 21
20 24
16 22
17 21
9 24

출력

#1 4
#2 4
#3 5

My Sol

def select(i, cnt):
    global time, maxCnt
    if i == dl:
        maxCnt = max(maxCnt, cnt)
        return

    select(i+1, cnt)

    s, e = dockLst[i]
    if time[s]:
        maxCnt = max(maxCnt, cnt)
        return
    for k in range(s, e):
        time[k] = 1
    select(i+1, cnt+1)
    for k in range(s, e):
        time[k] = 0

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    seLst = [100]*25
    for _ in range(N):
        s, e = map(int, input().split())
        seLst[s] = min(e, seLst[s])

    dockLst = []
    dl = 0
    for i in range(25):
        if seLst[i] !=100:
            dockLst.append((i, seLst[i]))
            dl += 1

    time = [0]*25
    maxCnt = 0
    select(0, 0)

    print(f'#{tc} {maxCnt}')

24시간을 인덱스로 지정하고, 시작 시간마다 종료 시간을 값으로 배정한다. 같은 시작 시간이라면 종료 시간이 더 짧은 신청만 남기면 되므로 이에 대한 로직을 구성하고, 트리를 이용해 종료 시간만큼 이동해서 해당 시간대의 도크를 선택할지 안할지를 결정하는 방식으로 최적해를 구한다.

결과

PASS