Search

PGS 택배 배달과 수거하기

생성일
2024/11/30 04:16
태그
그리디 알고리즘

문제 설명

•
트럭이 한 번에 최대 capcap개의 상자를 싣고 nn개의 집에 배달 및 수거를 완료하며 물류창고로 돌아올 최소 이동 거리를 구하는 문제

예제 입력/출력

cap
n
deliveries
pickups
result
4
5
[1, 0, 3, 1, 2]
[0, 3, 0, 4, 0]
16
2
7
[1, 0, 2, 0, 1, 0, 2]
[0, 2, 0, 1, 0, 2, 0]
30

제약 조건

•
1≤cap≤501 ≤ cap ≤ 50
•
1≤n≤100,0001 ≤ n ≤ 100,000
◦
0≤0 ≤ deliveries 원소 ≤50≤ 50
◦
0≤0 ≤ pickups 원소 ≤50≤ 50

문제 풀이

접근1 브루트 포스 - 상한 O(n!n!)
접근2 그리디 - O(n)O(n)

풀이 코드

풀이1 그리디 - O(n)O(n)
풀이2 그리디(풀이1 시간 복잡도 개선) - O(n)O(n)

참고 자료