[백준] 순회강연 - 2109
링크
문제
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
풀이
처음에는 문제를 접근했을 때 d일 안에 와서 강연을 해 주면 p만큼의 강연료를 지불한다는 것으로 풀지않고 d일에 와서 강연을 해주면 p만큼의 강연료를 지불한다라고 읽고 문제를 처음부터 잘못 접근하였다;;;;
후 다음부턴 꼼꼼하게 읽자!!
- 우선순위 큐안에 제네릭 타입을 int배열로 잡아준다.
- 최대의 p값을 가져와야 하기에 비용 기준으로 내림차순 정렬
- 비용이 같으면 d를 내림차순으로 정렬(d일 안에 해야 하는 것이기 때문)
- boolean배열 값을 잡아준다.(강연을 했다는 것을 표시하기 위해)
- 다음 이중for문 안쪽 for문은 day부터 줄여나가면서 방문을 하지 않은 날짜에 true값을 설정해주고 result값을 더해나간다.
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
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());
boolean check[]=new boolean[10001];
int result=0;
if(n==0)
{
System.out.println(0);
return ;
}
PriorityQueue<int[]> pq=new PriorityQueue<int[]>
(new Comparator<int[]>() {
public int compare(int[] o1, int[] o2)
{
if(o1[0] < o2[0])
return 1;
else if(o1[0]==o2[0])
return o2[1]-o1[1];
return -1;
}
});
for(int i=0; i<n; i++)
{
StringTokenizer st=new StringTokenizer(br.readLine());
int num1=Integer.parseInt(st.nextToken());
int num2=Integer.parseInt(st.nextToken());
pq.add(new int[] {num1, num2});
}
for(int i=0; i<n; i++)
{
int arr[]=pq.poll();
int price=arr[0];
int day=arr[1];
for(int j=day; j>=1; j--)
{
if(!check[j])
{
check[j]=true;
result+=price;
break;
}
}
}
System.out.println(result);
}
}
Author And Source
이 문제에 관하여([백준] 순회강연 - 2109), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@ehdcks3421/백준-순회강연-2109
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
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());
boolean check[]=new boolean[10001];
int result=0;
if(n==0)
{
System.out.println(0);
return ;
}
PriorityQueue<int[]> pq=new PriorityQueue<int[]>
(new Comparator<int[]>() {
public int compare(int[] o1, int[] o2)
{
if(o1[0] < o2[0])
return 1;
else if(o1[0]==o2[0])
return o2[1]-o1[1];
return -1;
}
});
for(int i=0; i<n; i++)
{
StringTokenizer st=new StringTokenizer(br.readLine());
int num1=Integer.parseInt(st.nextToken());
int num2=Integer.parseInt(st.nextToken());
pq.add(new int[] {num1, num2});
}
for(int i=0; i<n; i++)
{
int arr[]=pq.poll();
int price=arr[0];
int day=arr[1];
for(int j=day; j>=1; j--)
{
if(!check[j])
{
check[j]=true;
result+=price;
break;
}
}
}
System.out.println(result);
}
}
Author And Source
이 문제에 관하여([백준] 순회강연 - 2109), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ehdcks3421/백준-순회강연-2109저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)