백준 8980 택배
-
백준 8980 택배Algorithm/BOJ 2020. 7. 20. 16:10
출처: www.acmicpc.net/problem/8980 분류: 그리디 접근방식 출발 도시와 도착 도시, 용량이 적혀있는 택배 목록이 주어질 때 배달할 수 있는 최대 용량을 구하는 문제입니다. 단, 한번 지나온 마을은 다시 돌아갈 수 없습니다. 핵심 포인트는 다음 2가지 입니다. 문제의 핵심은 도착 도시를 기준으로 정렬 각 도시에서 적재 가능한 용량 체크 특히 도착 도시를 기준으로 정렬하는 것이 핵심인데요, 도착 도시를 기준으로 정렬했기 때문에 가장 먼저 내릴 수 있는 택배를 우선적으로 배달할 수 있습니다. 예를 들어, 3 60 3 1 3 50 1 2 30 2 3 60 이렇게 주어질 때 도착 기준으로 정렬합니다. 1 2 30 1 3 50 2 3 60 가장 먼저 도착하는 2번 마을에 배달해야 할 양 30..