반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 카카오 메뉴리뉴얼
- 프로그래머스 누적합
- 프로그래머스 2차원동전뒤집기
- 프로그래머스 스타수열
- 비트마스킹
- 확률과우도
- MLE
- 카카오 코테 메뉴리뉴얼
- 데이터축소
- 프로그래머스
- 딥러닝파라미터
- 딥러닝학습
- 메뉴리뉴얼 파이썬
- 프로그래머스광고삽입
- 모델경량화
- 딥러닝
- 스타수열 파이썬
- 광고삽입 파이썬
- 딥러닝 가중치 갱신
- k겹 교차검증
- 과적합방지
- 자율성장 인공지능
- 인공신경망 학습
- AI경량화
- 인공지능 경진대회
- 머신러닝 학습 검증
- 2차원동전뒤집기
- 스타수열
- 프로그래머스 2차원동전뒤집기 파이썬
- 로지스틱 최대우도
Archives
- Today
- Total
머신러닝 개발자의 러닝머신
[백준 8980] 택배 (Python) 본문
반응형
유형: 그리디
해결 아이디어
- 도착이 빠른 순서대로 택배 리스트 재정렬
: 그리디 아이디어, 1번 마을부터 출발하므로 도착이 가장 짧은 순서대로 정렬해서 순서대로 짐을 싣는다면
가장 짧은 기간동안 물건을 가지고 있을 수 있다.
(처음 풀때는 (출발, 도착) 튜플을 정렬해서 출발지와 도착지가 모두 빠른 순서대로 검사해나갔지만 도착이 빠른
순서대로 재정렬하면 됨.)
구현
- able_remain: 각 마을 번호의 위치에서 실을 수 있는 무게, 남아 있는 용량 리스트
- 동작과정
(1) 도착이 빠른 주문부터 순서대로 확인하면서 from->to 경로를 지날 수 있는 남은 용량을 구한다
(2) 옮길 최종 무게를 결정한다 = min(지날 수 있는 남은 용량, 주문 물건의 무게)
(3) 옮긴다. 지나오는 마을의 남은 용량을 빼준다.
코드
N, C = map(int, input().split()) #마을, 트럭용량
M = int(input()) #보내는 박스 정보 갯수
info_lst = []
for _ in range(M):
info_lst.append(tuple(map(int, input().split())))
info_lst.sort(key=lambda x: x[1]) #도착 순서가 빠른 순서로 정렬 -> 물건을 최대한 짧게 들고 있을 수 있도록
able_remain = [C]*(N+1) #마을 번호 1번부터 시작
result = 0 # 총 옮긴 물건의 무게의 합
for i in range(M):
a, b, w = info_lst[i] #from, to 마을 번호, 옮길 물건의 무게
tmp = C # 옮길 물건
# a->b 까지 옮길 수 있는 용량(남아 있는 용량)
for j in range(a, b):
tmp = min(tmp, able_remain[j])
# 옮길 수 있는 용량 = min(옮길 수 있는 남아있는 용량, 옮길 물건의 무게)
tmp = min(tmp, w)
# 실제 물건을 옮기면서 remain 에서 물건의 무게만큼 빼주어 남은 용량을 갱신한다
for j in range(a, b):
able_remain[j] -= tmp
result += tmp
print(result)
반응형
'알고리즘 > boj' 카테고리의 다른 글
[백준 9465] 스티커(Python) (0) | 2023.01.25 |
---|---|
[백준 1543] 문서검색 (Python) (0) | 2023.01.11 |
1655: 가운데를 말해요 (Python) (0) | 2022.07.28 |
15685: 드래곤 커브 (Python) (0) | 2022.07.28 |
12865: 평범한 배낭 (Python) (0) | 2022.07.27 |