[8980] 택배

2023. 6. 10. 23:51·Coding Test/Geedy
728x90
 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

 

분석

  • N ≤ 100, M ≤ 1,000, C ≤ 2,000
  • 도착 지점(받는 마을)이 먼저인 순으로 정렬

풀이

"""
조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
조건 3: 박스들 중 일부만 배송할 수도 있다.
마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때,
트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다.
다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다
다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다.

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력
"""
import sys
input=sys.stdin.readline

# 마을수, 트럭용량
N,C=map(int,input().split())
M=int(input())
delList=[]
for i in range(M):
    s,e,w=map(int, input().split())
    delList.append((s,e,w))

# 도착지 기준 정렬
delList.sort(key=lambda x: (x[1]))
# print(delList)

v=[0]*(N+1)  # 현재 트럭에 싣은 양
cnt = 0
for f, t, s in delList:
    box = s
    # 트럭 공간 체크
    for i in range(f, t):
        if v[i] + box >= C:  # 트럭에 다 싣을수 없다면
            box = C-v[i]  # 트럭 여유공간
    for i in range(f, t):
        v[i]+=box
    cnt += box  # 배달 택배양 추가

print(cnt)

 

 

 

 

728x90
저작자표시 비영리 변경금지
'Coding Test/Geedy' 카테고리의 다른 글
  • [1700] 멀티탭 스케줄링 (플러그 교체 최소 횟수)
  • [2170] 선 긋기 (선의 총 길이 구하기)
  • [15903] 카드 합체 놀이 (우선순위 큐)
  • [1439] 뒤집기 (문자열)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    알고리즘
    그래프
    조합
    재귀
    백준
    트리
    구현
    다익스트라
    최대공약수
    프로그래머스
    월간코드챌린지
    플로이드워셜
    DFS
    힙
    덱
    최단거리
    BFS
    정렬
    최소신장트리
    동적계획법
    스택
    이분탐색
    파이썬
    Algorithm
    자료구조
    LIS
    그리디
    구간합
    큐
    DP
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[8980] 택배
상단으로

티스토리툴바