알고리즘/문제풀이

그리디알고리즘(시간 관리/S1)

문승주 2022. 11. 10. 00:39
반응형

1. 문제

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

2. 입력

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

 

3. 출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

4. 코드

import sys

n = int(sys.stdin.readline())
list = []
for _ in range(n):
  work, end = map(int,sys.stdin.readline().strip().split())
  start = end - work
  list.append((end, work, start))
# 종료 시간기준으로 내림차순 정렬
list.sort(reverse=True)
# 처음 시작시간
result = list[0][2]
for i in range(1,n):
  # 시작시간이 다음 종료시간보다 앞이면 다음 시작시간을 결과값에 대입
  if result > list[i][0]:
    result = list[i][2]
  # 시작시간이 다음 종료시간과 같거나 뒤면 결과값에 작업시간을 뺄셈
  else:
    result -= list[i][1]

  # 결과값이 0 이하가 되면  -1 출력
  if result < 0:
    result = -1
    break
print(result)

 

5. 풀이설명

① 끝내야 할 시간에서 일하는데 걸리는 시간만큼 마이너스하여 최대 시작시간을 구한다.

 

② 반복문을 돌면서 끝내야 할 시간, 일하는데 걸리는 시간, 최대 시작시간을 리스트에 추가하고 끝내야할 시간의 내림차순으로 리스트를 정렬한다.

 

③ 종료시간이 가장 큰 리스트의 최대 시작 시간을 결과값에 대입

 

④ 리스트로 반목문을 돌면서 결과값보다 최대 시작시간이 앞인 시간을 결과값에 대입한다.

 

⑤ 결과값보다 최대시작시간이 뒤거나 같은 리스트는 결과값에서 일하는데 걸리는 시간만큼을 빼준다.

 

⑥ 결과값이 0이하가 되면 -1을 출력하고 아니면 결과값을 출력한다.

 

6. 느낀점

처음 접근할때 정렬을 하지 않은 상태로 최소시간을 구하려고 해서 문제를 풀지 못했다. 종료시간을 기준으로 내림차순 정렬을 하고 문제해결을 하니 쉽게 풀렸다.

반응형