[Python] 백준 6068 - 시간 관리하기

https://www.acmicpc.net/problem/6068

6068번: 시간 관리하기

 

---

해결방법

주어진 입력을 시간 순서대로 정렬을 하고, '늦잠'이라는 여유 부릴 시간에 대해서 늦잠 시간이 성립하는지 알아본다.

풀이

아래는 백준 예제 입력을 풀이한 것이다.

now를 구하는 방법은 첫 할 일의 '마감시간(deadline) - 일하는 데 필요한 시간(need = T)' 값이다.

i 번째 일을 하는데에 대한 시간은 앞으로 'deadline_i'와 'need_i'로 표현하겠다. 

now에 대해서 now + need_1이 즉, i=1일땐 성립하므로, i=2인 때, now + (2_sigma_i=1 (need_i)) <= deadline_2 를 확인한다. 이 값도 True라면  i=3 일때를 확인한다. 그리고 이것을 일의 개수(n)만큼 i=1 ~ i=n까지 확인한다.

확인하는 도중 now + (n_sigma_i=1 (need_i)) <= deadline_n 이 성립하지 않는다면 어떡할까?

그럼 늦잠시간을 1만큼 줄여 다시 확인해본다.

이를 구현하는 방법은 아래 코드에서 보겠다.

늦잠이 overslept인줄 몰랐다. ㅠ now 말고 overslept이라고 명명할걸 그랬다

---

코드

works = int(input())

task = []
for i in range(works):
  times, limit = map(int,input().split())
  task.append([times,limit])

# 정렬하기.
for i in range(works-1):
  for k in range(i+1,works):
    if task[i][1] > task[k][1]:
      task[i], task[k] = task[k], task[i]
    elif task[i][1] == task[k][1]:
      if task[i][0] > task[k][0]:
        task[i], task[k] = task[k], task[i]

start = task[0][1] - task[0][0] #limit - times = start
t = start #늦잠 시간

while t>=0:
  suc_all = True
  for i in range(works):
    if start + task[i][0] > task[i][1]:
      t -= 1
      start = t
      suc_all = False
      break;
    start += task[i][0]
  # t일 때 모든 순회를 통과하면?
  # 그게 정답
  if suc_all:
    print(t)
    break

if t<0:
  print(-1)

코드 설명

1. 정렬하기

# 정렬하기.
for i in range(works-1):
  for k in range(i+1,works):
    if task[i][1] > task[k][1]:
      task[i], task[k] = task[k], task[i]
    elif task[i][1] == task[k][1]:
      if task[i][0] > task[k][0]:
        task[i], task[k] = task[k], task[i]

그냥 sort()를 사용했더니 틀렸다고 나온다. 정확한 이유는 모르겠다. 그래서 정렬을 구현했다.

task[i][0] : i번째 일의 작업시간

task[i][1] : i번째 일의 마감시간

만약 i번째 일의 마감시간이 k번째 일의 작업시간보다 오래걸린다면 그 둘의 자리를 바꿔준다.

그리고 만약 i번째와 k번째 일의 마감시간이 서로 같다면, 그 둘의 작업시간을 기준으로 더 짧게 걸리는 것을 앞으로 정렬한다. 그래야 최대한 효율적으로 일처리를 할 수 있게 된다.

2. 변수 설정

start = task[0][1] - task[0][0] #limit - times = start
t = start #늦잠 시간

 

 

늦잠을 자고서 일을 시작하는 시간을 start라고 했다. start까지 늦잠을 자므로 늦잠=start라고 생각하고 작성했다. start는 while문 안에서 지역변수로 사용될 예정이다. start가 while문 안에서만 사용되는 게 아니라면 while문에서

if start + task[i][0] > task[i][1]:

위 조건을 만족할때마다 start 값에 task[i][0]을 더해주기 때문에 값이 오염되기 때문이다.

그래서 start=t일 때 일을 제때 처리할 수 없으면 start를 t-1로 초기화하여 처음부터 다시 확인해보기 위해 t라는 변수를 새로 만들었다.

3. 반복문

while t>=0:
  suc_all = True
  for i in range(works):
    if start + task[i][0] > task[i][1]:
      t -= 1
      start = t
      suc_all = False
      break;
    start += task[i][0]
  # t일 때 모든 순회를 통과하면?
  # 그게 정답
  if suc_all:
    print(t)
    break

if t<0:
  print(-1)

• suc_all : 'start(=t) 만큼 늦잠을 자고 해야할 모든 일을 완수했다.' 라는 뜻의 변수이다.

아무리 빨라도 0시부터 일을 시작하므로 t가 음의 정수가 아닌 경우만 while을 실행한다. 만약 t<0이면 일을 할 수 없으므로 문제의 조건대로 -1 을 출력.

for 반복문 안의 조건문 안을 보자. 만약 마감시간안에 일을 처리할 수 있으면 start에 need_i를 더한다.

반대로 마감시간안에 일을 처리할 수 없으면(= now + (2_sigma_i=1 (need_i)) 이 마감시간을 넘긴다면), 늦잠시간 t에 일을 시작하면 결국 일을 모두 못한다는 소리이다. 그러므로 t = t-1인 시간으로 시뮬레이션해본다.