BOJ - 1826 연료 채우기

leehyunjon·2022년 6월 25일

Algorithm

목록 보기

72/162

Problem

Solve

해당 문제를 풀기 위해서는 현재 연료 수 P와 주유소에서 충전할수 있는 연료의 수 b의 합이 성경이 출발 지점에서 이동할수 있는 거리임을 찾아내야한다.

그 다음 P를 가지고 이동할수 있는 주유소 중 가장 많은 양의 연료를 충전할수 있는 주유소를 방문해야한다.
그러기 위해서는 거리순으로 정렬되어있는 주유소의 PriorityQueue< Soil > stations 와 P로 이동가능한 주유소 중 연료를 기준으로 내림차순되어있는 PriorityQueue< Integer > pq를 사용해야한다.

테스트케이스를 예시로 들어보자면 stations에 거리를 기준으로 내림차순 정렬을 한다.

기존 연료 P = 10이기 때문에 10이하에 있는 주유소를 pq에 저장한다. 그 중 연료를 가장 많이 채울수 있는 4를 P에 추가한다.

P가 14가 되었고 이동할 수 있는 거리 중 거리 11에 있는 주유소도 이동이 가능하기 때문에 pq에 5를 추가해준다. 그 중 연료를 가장 많이 채울수 있는 5를 P에 추가한다.

P가 19가 되었고 이동할 수 있는 거리 중 거리 15에 있는 주유소도 이동이 가능하기 때문에 pq에 10을 추가해준다. 그 중 연료를 가장 많이 채울수 있는 10을 P에 추가한다.

P가 29가 되었고 목적지인 L=25를 넘었기 때문에 방문한 주유소의 개수는 3개가 된다.

만약 L이 30이라면 pq에 남아있는 연료 2를 추가하여 이동하면 목적지까지 도달할수 있게 된다.
이 때 주유소의 개수는 4개가 된다.

Code

public class 연료채우기 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		//거리 기준 내림차순 정렬
		PriorityQueue<Soil> stations = new PriorityQueue<>();

		for(int i=0;i<N;i++){
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			stations.offer(new Soil(a,b));
		}

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int L = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());

		int answer = 0;
        //이동가능한 주유소 중 연료 기준 내림차순
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        //연료P가 L보다 크거나 같을때까지 반복
		while(P<L){
        	//이동할 주유소가 있고 그 주유소가 현재 연료로 이동가능하다면 pq에 추가해준다.
			while(!stations.isEmpty()&&stations.peek().pos<=P){
				pq.offer(stations.poll().fuel);
			}

			//P를 가지고 목적지에 도착하지 못했는데 이동가능한 주유소가 없다면 -1 반환.
			if(pq.isEmpty()){
				answer = -1;
				break;
			}

			//이동가능한 주유소가 있다면 그 중 충전할 수 있는 연료가 가장 많은 것을 P에 추가
			P += pq.poll();
			answer++;
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static class Soil implements Comparable<Soil>{
		int pos;
		int fuel;
		public Soil(int pos, int fuel){
			this.pos = pos;
			this.fuel = fuel;
		}

		@Override
		public int compareTo(Soil o1){
			return this.pos - o1.pos;
		}
	}
}