[BOJ] 백준 8980번 - 택배 (Python)

문제

문제 해결

마을에서 트럭이 택배를 수집할 때는 무조건 도착 배송지가 가까운 택배들부터 담는 것이 중요하다. 빠르게 순환이 되어야 또 다른 택배를 실을 수 있기 때문이다.

또한 각 point에 도착했을 때 택배를 먼저 unload한 뒤에 load를 해야하는 순서도 꼭 지켜져야 한다.

우선 입력이 [start_point, dest_point, load] 로 된 M개의 박스 정보를 sort() 하여 start_point, dest_point, load 순으로 정렬한다. 이렇게 되면, 택배가 처리되는 순서대로 정렬이 완료된다.

그리고 각 point별로 트럭이 움직이므로 point마다 반복문을 돌리고, 각 point에서는 unload, load 순으로 코드가 진행된다.

첫번째 제출 답안

import sys

N, C = map(int, input().split())  #N:마을 수, C:트럭의 용량
M = int(input())  #M:택배의 최대 개수

point = 0  #좌표
load = 0  #택배 개수
cnt = 0  #배송한 택배 개수
task = list()  #배송 일정

for i in range(M):
  task.append(list(map(int, sys.stdin.readline().split())))
task.sort()

for point in range(1, N + 1):
  print("------------------")
  for order in task:
    print(order)
    # unload
    if order[1] == point:
      load -= order[2]
      cnt += order[2]
    # load
    if order[0] == point:
      if load + order[2] <= C:
        load += order[2]
      else:
        order[2] = C - load
        load += order[2]
print(cnt)

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20
------------------
[1, 2, 10]
[1, 3, 20]
[1, 4, 30]
[2, 3, 10]
[2, 4, 20]
[3, 4, 20]
------------------
[1, 2, 10]
[1, 3, 20]
[1, 4, 10]
[2, 3, 10]
[2, 4, 20]
[3, 4, 20]
------------------
[1, 2, 10]
[1, 3, 20]
[1, 4, 10]
[2, 3, 10]
[2, 4, 0]
[3, 4, 20]
------------------
[1, 2, 10]
[1, 3, 20]
[1, 4, 10]
[2, 3, 10]
[2, 4, 0]
[3, 4, 20]
70

제출은 결과인 70만 출력되도록 하면 된다.

하지만, 이 답안은 서브태스크의 최저점인 15점을 받았다…

따라서 다른 서브태스크들을 고려하여 다시 한 번 코드를 짜보았다.

두 번째 제출 답안

문제점을 발견했다!

트럭이 1부터 N까지의 마을을 차례로 방문하며 택배를 수집하는데, 이때 이전 마을에서 너무 목적지가 먼 택배를 load했다면 계속해서 그 칸을 차지하고 있는 상태가 발생한다. starvation..?

그렇다면 이전 마을에서 수집한 택배보다 목적지가 짧은 택배를 수집할 수 있을 경우 원래 있던 목적지가 먼 택배를 버려야 한다.

근데 택배 회사가 그래도 되나…? 버려진 택배는 어떡해? ‘이게 맞아..?’

즉, 지금 수집할 택배보다 먼 거리의 원래 택배들을 가장 먼 순서대로 현재 택배의 개수만큼 버려야 한다. (최대 N개)

그러면, 이전 마을에서 수집된 택배들에 현재 마을에서 수집할 택배들을 싹 모아놓고 거리가 가까운 순으로 C만큼만 뽑으면 되는 거 아닐까?

코드로 작성해보자.

제가 짠 코드는 정말 어떻게든 생각한 바를 구현하기만 하면 100점을 맞을 수는 있다를 보여드리기 위해 작성해 놓은 것이고, 다른 더 좋은 코드들이 많습니다..!

코드 설명은 생략합니다

import sys

N, C = map(int, input().split())  #N:마을 수, C:트럭의 용량
M = int(input())  # M:택배의 최대 개수

point = 0  # 좌표
loaded = 0  # 트럭에 실린 택배 개수
delivered = 0  # 배송한 택배 개수
parcel = list()  # 택배 리스트 (start_point, dest_point, parcel)
loaded_parcel = list()  # 실린 택배 리스트 (dest_point, parcel_ea)

for i in range(M):
  parcel.append(list(map(int, sys.stdin.readline().split())))
parcel.sort()

print("parcel = ", parcel)

for point in range(1, N + 1):
  # unload
  hit_parcel = list()
  for idx, delivery in enumerate(loaded_parcel):
    if delivery[0] == point:
      delivered += delivery[1]
      hit_parcel.append(idx)

  for idx in reversed(hit_parcel):
    del loaded_parcel[idx]

  # load
  for item in parcel:
    if item[0] == point:
      loaded_parcel.append([item[1], item[2]])

  loaded_parcel.sort()  # 배송지 빠른 순 정렬

  loaded = 0
  for idx, delivery in enumerate(loaded_parcel):
    loaded += delivery[1]
    if loaded > C:
      delivery[1] -= (loaded - C)
      if delivery[1] == 0:
        loaded_parcel = loaded_parcel[:idx]
        break
      else:
        loaded_parcel = loaded_parcel[:idx + 1]
        break
  print("loaded parcel = ", loaded_parcel)
  
print(delivered)

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20
parcel =  [[1, 2, 10], [1, 3, 20], [1, 4, 30], [2, 3, 10], [2, 4, 20], [3, 4, 20]]
loaded parcel =  [[2, 10], [3, 20], [4, 10]]
loaded parcel =  [[3, 10], [3, 20], [4, 10]]
loaded parcel =  [[4, 10], [4, 20]]
loaded parcel =  []
70

간결한 제출 답안

import sys

input = sys.stdin.readline
N, C = map(int, input().split())
M = int(input())

parcel = [list(map(int, input().split())) for _ in range(M)]
parcel.sort(key = lambda x: x[1]) # 가까운 배송지 순으로 정렬

delivered = 0
capacity = [C] * N # 마을 당 트럭이 수용가능한 박스 수

for start_point, dest_point, ea in parcel:
    minimum = C 
    # 각 주문의 시작점-도착점 사이 최소 수용 가능한 택배 수를 구한다
    for i in range(start_point, dest_point):
        minimum = min(minimum, capacity[i])
    # 현재 주문의 개수와 최소 수용 가능한 택배 수를 비교하여 구한다.
    minimum = min(minimum, ea)
    # 시작점부터 도착점 사이의 모든 마을에서 트럭이 수용 가능한 택배 수를 줄이고, 배송한 택배 수를 늘린다.
    for k in range(start_point, dest_point):
        capacity[k] -= minimum
    delivered += minimum

print(delivered)

고찰

문제를 보면 어떻게 풀어야 할 지 감이 딱 온다. 하지만 그렇게 풀다가 보면 계속해서 또다른 무언가를 계속해서 구현해나가야 한다. 굳이 비유하자면 수능 21번, 30번 같은 느낌.. 하지만 호흡이 길어도 끝까지 해내기만 하면 결국 정답은 되겠지만 참 부끄럽다. 남들이 간결하게 푼 문제를 풀이과정 더럽게 풀어낸 느낌.. 그리고 남들이 간결하게 쓴 코드들도 해석하는데 상당한 시간이 걸린다. 아직은 경험이 부족해서라고 생각하고, 계속해서 꾸준히 조금씩 풀어나가면 주먹구구식이 아닌, 세련되고 간결한 코드를 쓸 수 있겠지라고 생각하고 있다.