백준 1826번(JAVA)

아래 문제와 매우 비슷하다.

우선순위큐에 객체를 넣어서 객체끼리 비교할 줄 알면 수월하게 풀 수있다.

아래 문제도 같이 참고해서 보면 비슷한 유형이라는걸 알 수 있다.

2021.04.30 - [백준 문제풀이(JAVA)/그리디 알고리즘] - 백준 1781번(JAVA)

백준 1781번(JAVA)

우선 입력값을 거리가 가장 작은게 앞에오도록(우선순위가 크게) 정렬한다.

이중 while문을 사용한다

첫 번째 while문에서는 (현재가지고연료<목적지) 라는 조건을 달아준다.

마지막에 입력받는 L,P가 예를들어 10,20이면 현재 가지고있는 연료로 목적지까지 한번에 가므로 주유소를

들릴필요가없어서 바로 while문이 깨진다.

그리고 현재 가지고 있는 연료로 갈 수 있는 주유소의 기름양을모두 우선순위 q에넣는다

참고로 q는 내림차순으로 가장 큰 양의 기름이 큰 우선순위를 갖는다.

 

 근데 여기서 q가 비어있다는 뜻은 바로 현재 가지고있는 기름으로는 다음 주유소까지 못 간다는 뜻이다.

바로 result값에 -1을 넣어주고 while문을 깨준다.

만약 비어있지 않다면 q를 하나 poll해주고 현재 가지고 있는 기름의 양에 해당값을 더해준다.

그리고 마지막으로 result++,방문한 주유소의 숫자를 증가시킨다.

 

 

소스코드

import java.util.*;
import java.io.*;
class oil_bank implements Comparable<oil_bank>
{
	int dis;
	int oil;
	public oil_bank(int dis,int oil)
	{
		this.dis=dis;
		this.oil=oil;
	}
	@Override
	public int compareTo(oil_bank o)
	{
		return dis-o.dis;//거리가 짧은게 큰 우선순위를 가진다
	}
}
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		PriorityQueue<oil_bank> info=new PriorityQueue<oil_bank>();//주유소 정보가 담겨있다.
		String[] s;
		for(int i=0;i<N;i++)
		{
			s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			info.add(new oil_bank(a,b));
		}
		s=br.readLine().split(" ");
		int L=Integer.parseInt(s[0]);//마을까지의 거리
		int P=Integer.parseInt(s[1]);//현재 갖고있는 기름의 양
		int result=0;//결과값
		PriorityQueue<Integer> q=new PriorityQueue<Integer>(Collections.reverseOrder());//가장 큰 기름의 양이 큰 우선순위 가짐
		while(P<L)//현재 가지고있는연료가 거리보다 작을때만
		{
			while(!info.isEmpty()&&P>=info.peek().dis)//처음 가지고 있는 연료로 갈 수 있는 주유소 쭉 입력받는다
			{
				oil_bank temp=info.poll();
				q.add(temp.oil);
			}
			if(q.isEmpty())//현재 가지고 있는 연료로 갈 수 있는 주유소가 없다면...
			{
				result=-1;
				break;
			}
			P=P+q.poll();
			result++;
		}
		System.out.println(result);
	}
}

댓글과 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러 후원 부탁드립니다~!