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
- boot sequence
- 임베디드
- BHS
- 다익스트라
- 응용 계층
- dp
- 네트워크
- baekjoon
- DB
- 전송 계층
- Database
- BST
- Transport layer
- Application Layer
- Network
- 문제풀이
- ps
- 부트시퀀스
- STL
- swea
- Djikstra
- 릿코드
- 백준
- 프로그래머스
- 데이터베이스
- leetcode
- 관계형 모델
- C++
- 자료구조
- Embedded
Archives
- Today
- Total
BOBO's Note
[ 프로그래머스 ] 라면공장 본문
https://programmers.co.kr/learn/courses/30/lessons/42629
풀이 방법
하루에 밀가루를 1톤씩 사용하므로, 밀가루 재고가 amount일 때 현재 날짜가 amount 보다 크거나 같으면 밀가루 재고가 부족하다. 따라서 이 경우에는 그 전에 밀가루를 미리 구매해야 한다.
이때, 밀가루 구매 횟수를 최소화하기 위해서는 한번에 최대한 많이 구매할 수 있는 날에 구매해야 한다. 따라서 우선순위 큐를 두어서 한번에 구매할 수 있는 최대 수량을 저장해나간다. 그리고 현재 날짜까지 사용할 수 있는 충분한 양의 밀가루를 구매한다.
while(amount <= dates[i]){
amount += pq.top();
pq.pop();
answer++;
if(amount >= k) return answer;
}
한편, 밀가루 재고가 딱 떨어지는 날에 구매해야만 하는 경우가 있을 수 있다. 이 경우에는 우선순위 큐가 비어있기 때문에 먼저 우선순위 큐에 추가하도록 한다. 그리고 그 날의 수량을 -1로 업데이트하여 우선순위 큐에 한번 더 추가하더라도 문제 없도록 한다.
if(amount == dates[i]){
pq.push(supplies[i]);
supplies[i] = -1;
}
while(amount <= dates[i]){ ... }
pq.push(supplies[i]);
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ Baekjoon ] 1103. 게임 (0) | 2020.09.10 |
---|---|
[ 프로그래머스 ] 가장 먼 노드 (0) | 2020.07.09 |
[ LeetCode ] 53. Maximum Subarray (0) | 2020.07.04 |
[ 프로그래머스 ] 큰 수 만들기 (0) | 2020.06.30 |
[ LeetCode ] 98. Validate Binary Search Tree (0) | 2020.06.28 |
Comments