문제 바로가기
풀이가 정말 그리디스러운? 그런 문제였다. 서브태스크 문제는 처음이라 한 번 시도해보았는데 재밌는 것 같다. 로직을 생각하는 것은 그닥 시간이 오래걸리지 않았는데 데이터를 어떻게 저장할지 고민하다가 시간이 훅 가버렸다. 처음엔 별 고민없이 최솟값을 뽑아서 비교하는 거니까 heapq를 사용하여 리스트에 저장했는데 이게 문제가 되었다.
간과한 점은 단순히 힙정렬의 시간복잡도가 O(logn)이니까 리스트를 정렬하는 것보다 빠를 것이라고 생각했다는 것이었다. 매번 리스트에서 요소를 넣고 빼는 과정에서 계속 O(logn) 만큼의 시간이 걸리면서 1차에 75점을 받았다.
2차 시도에서는 양방향 큐를 사용하여 리스트를 계속 정렬된 상태를 유지시키는 방식으로 처리했더니 100점을 받을 수 있었다.
노동을 좀 많이 하긴 했지만 그래도 이 문제를 풀면서, 힙정렬의 시간복잡도에 대해 다시 생각해볼 수 있었던 것 같다.
🧐 접근
우선, 트럭에 싣을 수 있는 용량이 정해져 있다면, 최대한 다 채워서 가는게 무조건 이득이라고 생각하였다. 이 문제의 핵심은 짐을 얼마나 싣을 지를 결정하는 시점이 짐을 내릴 때라는 것이다.
그래서, 트럭을 타고 각 지점에 도착할 때마다 일단 최대한 빨리 짐을 내릴 수 있는 것들로 선택을 바꿔주는 것이다.
즉!! 이기적으로, 짐을 일단 담고 필요없으면 아무 곳에나 버려주는 것이다.
- input
길이가 n+1인 places 리스트에 각 지점마다 내려야하는 짐 위치와 개수를 기록해둔다. 담는 위치를 기준으로 테이블을 만든 이유는 어차피 트럭이 담는 위치가 가까운 순서대로 이동하기 때문이다. 그리고 트럭에 어떤 짐을 담았는지 알아야 하기 때문에 truck = [] 생성, 트럭의 용량이 정해져 있기 때문에 얼마나 싣었는지 carry 라는 변수에 저장, 그리고 짐을 내릴 때 결과를 기록해둘 rst 변수 정의.
import sys
from collections import deque
input = sys.stdin.readline
n, c = map(int, input().split())
m = int(input())
places = [[] for _ in range(n+1)]
for _ in range(m):
s, e, v = map(int, input().split())
places[s].append([e, v]) # 어디에 몇개 내려야 하는지
truck = deque([]) # 어디서 내리는지, 얼마나 내리는지
carry = 0
rst = 0- 트럭을 이동시키자~
-
트럭을 위치가 1인 곳부터 n인 곳까지 차례로 방문해주자.
for i in range(1, n+1): -
각 지점에 도착하자마자 우선 내릴 짐이 있다면 짐을 내려주고 rst를 업데이트!
if carry > 0: while truck: if truck[0][0] == i: tmp = truck.popleft()[1] carry -= tmp rst += tmp else: break -
내릴 거 다 내렸다면, 이제 각 지점마다 싣어야 짐을 트럭에 꽉꽉 채워넣자.
우선, 싣어야 할 짐을 data라는 리스트로 받아오고 내리는 곳을 기준으로 정렬해주자.data = deque(sorted(places[i])) -
만약 data에 짐이 있다면, 현재 트럭에 있는 짐과 data에 있는 짐을 구분없이 새 트럭에 다시 내리는 지점 기준으로 꽉꽉 채워 담아주는 것이다.
if data: # 트럭에 뭐라도 있으면 트럭에 있는 것과 현재 위치에 있는 것들을 비교해서 새 트럭에 다시 담아 new_truck = deque([]) new_carry = 0 while carry <= c and (truck or data): truck_e = 1e9 data_e = 1e9 if truck: truck_e, truck_v = truck[0][0], truck[0][1] if data: data_e, data_v = data[0][0], data[0][1] space = c - new_carry if truck_e > data_e: # 자리가 있다면 다 담고 if space > data_v: new_carry += data_v new_truck.append(data.popleft()) # 자리가 부족하다면 남은 공간 만큼만 담아 else: new_carry = c new_truck.append([data[0][0], space]) break else: if space > truck_v: new_carry += truck_v new_truck.append(truck.popleft()) # 자리가 부족하다면 남은 공간 만큼만 담아 else: new_carry = c new_truck.append([truck[0][0], space]) break truck = new_truck carry = new_carry print(rst)
💻 1차 시도 (75점)
import sys
import heapq
input = sys.stdin.readline
n, c = map(int, input().split())
m = int(input())
places = [[] for _ in range(n+1)]
for _ in range(m):
s, e, v = map(int, input().split())
places[s].append([e, v]) # 어디에 몇개 내려야 하는지
truck = [] # 어디서 내리는지, 얼마나 내리는지
carry = 0
rst = 0
for i in range(1, n+1):
# 만약 이 장소에서 내릴 것이 있다면
if carry > 0:
while truck:
if truck[0][0] == i:
tmp = heapq.heappop(truck)[1]
carry -= tmp
rst += tmp
else:
break
# 음.. 현재 트럭에 있는 것 중 가장 먼저 내려야 하는 것과 지금 싣는 것들을 비교
data = places[i]
heapq.heapify(data)
# 트럭에 아무것도 없다면 그냥 담아
if carry == 0:
while (carry <= c) and data:
tmp = heapq.heappop(data)
space = c - carry
# 자리가 있다면 다 담고
if space > tmp[1]:
carry += tmp[1]
heapq.heappush(truck, tmp)
# 자리가 부족하다면 남은 공간 만큼만 담아
else:
carry = c
heapq.heappush(truck, [tmp[0], space])
break
elif data:
# 트럭에 뭐라도 있으면 트럭에 있는 것과 현재 위치에 있는 것들을 비교해서 새 트럭에 다시 담아
new_truck = []
new_carry = 0
while carry <= c and (truck or data):
truck_e = 1e9
data_e = 1e9
if truck:
truck_e, truck_v = truck[0][0], truck[0][1]
if data:
data_e, data_v = data[0][0], data[0][1]
space = c - new_carry
if truck_e > data_e:
# 자리가 있다면 다 담고
if space > data_v:
new_carry += data_v
heapq.heappush(new_truck, heapq.heappop(data))
# 자리가 부족하다면 남은 공간 만큼만 담아
else:
new_carry = c
heapq.heappush(new_truck, [data[0][0], space])
break
else:
if space > truck_v:
new_carry += truck_v
heapq.heappush(new_truck, heapq.heappop(truck))
# 자리가 부족하다면 남은 공간 만큼만 담아
else:
new_carry = c
heapq.heappush(new_truck, [truck[0][0], space])
break
truck = new_truck
carry = new_carry
print(rst)💻 최종 코드 (100점)
import sys
from collections import deque
input = sys.stdin.readline
n, c = map(int, input().split())
m = int(input())
places = [[] for _ in range(n+1)]
for _ in range(m):
s, e, v = map(int, input().split())
places[s].append([e, v]) # 어디에 몇개 내려야 하는지
truck = deque([]) # 어디서 내리는지, 얼마나 내리는지
carry = 0
rst = 0
for i in range(1, n+1):
# 만약 이 장소에서 내릴 것이 있다면
if carry > 0:
while truck:
if truck[0][0] == i:
tmp = truck.popleft()[1]
carry -= tmp
rst += tmp
else:
break
# 음.. 현재 트럭에 있는 것 중 가장 먼저 내려야 하는 것과 지금 싣는 것들을 비교
data = deque(sorted(places[i]))
if data:
# 트럭에 뭐라도 있으면 트럭에 있는 것과 현재 위치에 있는 것들을 비교해서 새 트럭에 다시 담아
new_truck = deque([])
new_carry = 0
while carry <= c and (truck or data):
truck_e = 1e9
data_e = 1e9
if truck:
truck_e, truck_v = truck[0][0], truck[0][1]
if data:
data_e, data_v = data[0][0], data[0][1]
space = c - new_carry
if truck_e > data_e:
# 자리가 있다면 다 담고
if space > data_v:
new_carry += data_v
new_truck.append(data.popleft())
# 자리가 부족하다면 남은 공간 만큼만 담아
else:
new_carry = c
new_truck.append([data[0][0], space])
break
else:
if space > truck_v:
new_carry += truck_v
new_truck.append(truck.popleft())
# 자리가 부족하다면 남은 공간 만큼만 담아
else:
new_carry = c
# heapq.heappush(new_truck, [truck[0][0], space])
new_truck.append([truck[0][0], space])
break
truck = new_truck
carry = new_carry
print(rst)👍 제출
