[백준] 1263번: 시간 관리 (파이썬)

✅문제: 1263번

📌개념정리

(1) 그리디 알고리즘 (Greedy Algorithm)

• 정의: 문제를 해결하는 데 있어 매 순간 최적의 선택을 함으로써 전체 문제의 최적해를 도출하는 알고리즘
• 작업들의 마감 시간을 기준으로 정렬한 뒤, 가장 늦게 시작할 수 있는 시간부터 계산하여 모든 작업을 수행할 수 있는지 확인하는 방식으로 해결할 수 있음.

(2) 정렬

• 정의: 데이터를 특정 기준에 따라 재배열하는 작업
• 작업을 마감 시간 기준으로 정렬하여, 가장 늦게 마감해야 하는 작업부터 역순으로 스케줄링할 수 있음.

📌문제풀이

주어진 작업의 소요 시간과 마감 시간을 기반으로 모든 작업을 수행할 수 있는 가장 늦은 시작 시간을 계산하는 문제임. 각 작업은 소요 시간과 마감 시간이 주어지며, 모든 작업을 마감 시간 내에 끝낼 수 있는지를 판단함.

1. 입력 데이터를 작업 리스트로 정리
   • 각 작업의 소요 시간 T와 마감 시간 S를 입력받아 리스트 형태로 저장함.
   • 작업 리스트를 마감 시간 S를 기준으로 내림차순 정렬하여, 가장 늦게 마감해야 하는 작업부터 처리함.
2. 최대 시작 시간 계산
   • 초기 최대 시작 시간을 가장 늦은 마감 시간으로 설정함.
   • 각 작업을 역순으로 처리하며, 작업을 완료할 수 있는 가장 늦은 시간을 계산함.
   • 계산된 값에서 작업 소요 시간을 빼며, 다음 작업의 최대 시작 시간을 갱신함.
3. 결과 반환
   • 모든 작업이 0 이상의 시작 시간에서 수행 가능하면 해당 값을 반환함.
   • 그렇지 않으면 -1을 반환하여 작업 완료가 불가능함을 표시함.

def time(tasks, n):
    # 마감 시간에 따라 내림차순 정렬
    tasks.sort(reverse=True, key=lambda x: x[1])

    max_start_time = tasks[0][1]  # 초기 최대 시작 시간 설정
    for duration, deadline in tasks:
        latest_finish_time = min(max_start_time, deadline)
        max_start_time = latest_finish_time - duration

    return max_start_time if max_start_time >= 0 else -1

예제 입출력을 확인하면 아래와 같음.

# 예제 입력 1 
4
3 5
8 14
5 20
1 16

 

• 주어진 작업 리스트:  [(3,5),(8,14),(5,20),(1,16)]

1. 작업 리스트를 마감 시간 기준으로 정렬: [(5,20),(1,16),(8,14),(3,5)]
2. 계산
   • 작업 (5,20):
     최대 시작 시간 = 20 − 5 = 15
   • 작업 (1,16):
     최대 시작 시간 = min⁡(15,16) − 1 = 14
   • 작업 (8,14):
     최대 시작 시간=min⁡(14,14) − 8 = 6
   • 작업 (3,5):
     최대 시작 시간=min⁡(6,5) − 3 = 2
3. 최종 최대 시작 시간: 2

# 예제 출력 1
2

📌후기

• 작업의 최대 시작 시간을 거꾸로 계산하는 방식이 새로웠으며, 작업들을 정렬하여 역순으로 처리하는 그리디 전략을적용할 수 있었음.