[문제풀이] 라면공장

업데이트:

문제 링크 : 라면공장

풀이 시간 : 20분

1. 문제 풀이

최소한의 밀가루 공급 횟수를 찾는 문제

현재부터 버틸 수 있는 날까지 최대 공급을 더해주면서

버틸 수 있는 날이 자체 생산(k 일)을 넘길 때까지 반복

Heap을 이용하여 최대 공급량을 뽑아 낸다.

1) 버틸 수 있는 날이 k 이상이면 종료

2) 버틸 수 있는 날까지 공급 가능한 밀가루 양을 Heap 넣는다.

3) Heap에서 poll() 통해 가장 많은 공급량을 뽑아서 현재 밀가루 양에 더한다.

1~3번 반복을 통해 공급 횟수를 찾는다.

2. 소스 코드

    static public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.intValue()-o1.intValue();
			}
		});
        
        int pivot_dates = 0;
        // 며칠까지 버틸 수 있는지
        int sum = stock;
        while(true) {
        	// 다시 밀가루가 공급되는 날보다 커지면 종료
        	if(sum>=k) {
        		break;
        	}
        	while(pivot_dates<dates.length) {
        		// 최대 버틸 수 있는 날 전까지 공급 받을 수 있는 날 검사
        		if(dates[pivot_dates]<=sum) {
        			// 공급 받을 수 있는 양 저장
        			q.add(supplies[pivot_dates]);
        			pivot_dates++;
        		}else {
        			break;
        		}
        	}
        	// 최대 버틸 수 있는 날까지 최대의 공급량을 더한다.
        	sum += q.poll();
        	answer++;
        }
        return answer;
    }

3. 후기

Heap을 통해 최대한의 공급량을 뽑아 내는 문제 였다

참고