[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2109번, 순회강연

문제 링크

2109번: 순회강연

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 하루에 1곳에서만 강연을 할 수 있습니다.

2. n개의 강연이 주어지며, p는 제시한 금액, d는 강연 진행 제한일입니다.

3. 강연을 통해 최대한 돈을 벌수 있는 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 강연에 대한 정보를 우선순위 큐로 정렬한 정보를 순차적으로 탐색합니다.

 

3. 탐색이 종료된 뒤 얻은 금액을 결과로 출력합니다.

 

 

강연 정보 탐색.

 

우선순위 큐에서 금액 기준 내림차순 정렬!

 

금액이 같을 때에는 제한일이 높은 것을 기준으로 정렬!

 

각 날짜에 강연을 진행하는지 확인하는 배열 boolean[]을 사용하였습니다.

 

탐색 진행

 

우선순위 큐에 있는 강연에 정보를 순서대로 받습니다.

 

예를 들어

 

받은 강연의 정보 : p = 20, d = 3일 때

 

boolean[3] = true로 변경됩니다.

 

이후 받은 강연의 정보 : p = 10, d = 3일 때

 

boolean[3]은 이미 true이기 때문에 boolean[2] = true가 됩니다.

 

결과적으로 금액이 비싼것부터 최대한 강연을 진행하도록 합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

N = 7

 

	강연 1	강연 2	강연 3	강연 4	강연 5	강연 6	강연 7
p(금액)	20	2	10	100	8	5	50
d(제한일)	1	1	3	2	2	20	10

 

2. 강연에 대한 정보를 우선순위 큐로 정렬한 정보를 순차적으로 탐색합니다.

우선순위 큐에 저장되어 정렬 진행!

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

 

탐색 진행!

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 4을 수행!

boolean[2] = true

받은 금액 : 100

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 7을 수행!

boolean[10] = true

받은 금액 : 50

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 1을 수행!

boolean[1] = true

받은 금액 : 20

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 3을 수행!

boolean[3]은 이미 true이기 때문에 그 전날 강연 수행!

boolean[2] = true

받은 금액 : 10

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 5을 수행하지 못한다.

boolean[2], boolean[1]은 모두 true이기 때문에 당일이나 전날에도 강연을 수행하지 못합니다.

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 6을 수행!

boolean[20] = true

받은 금액 : 5

 

	강연 4	강연 7	강연 1	강연 3	강연 5	강연 6	강연 2
p(금액)	100	50	20	10	8	5	2
d(제한일)	2	10	1	3	2	20	1

강연 2을 수행하지 못한다.

boolean[1]은 true이기 때문에 당일이나 전날에도 강연을 수행하지 못합니다.

 

 

3. 탐색이 종료된 뒤 얻은 금액을 결과로 출력합니다.

 

수행한 강연 : 강연 4, 강연 7, 강연 1, 강연 3, 강연 6

 

100 + 50 + 20 + 10 + 5 = 185

185을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 강연에 대한 정보를 띄어쓰기 기준으로 나누었습니다.
• 우선순위 큐에 강연에 대한 정보를 금액 기준 내림차순, 같을 때는 제한일 기준 내림차순으로 저장하였습니다.
• 우선순위 큐에 정보를 탐색하여 최대한 강연을 진행합니다.
• 최대한 강연을 진행한 금액의 합을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

결과코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
    //강연에 대한 정보 관련 클래스
    static class info implements Comparable<info>{
        int p, d;	//금액, 제한일
        //생성자
        public info(int p, int d){
            this.p = p;
            this.d = d;
        }
        //클래스 정렬관련
        @Override
        public int compareTo(info o) {
            if(this.p == o.p)	//금액이 같을 때 제한일 내림차순
                return o.d - this.d;
            return o.p - this.p;	//금액에 내림차순 정렬
        }

    }
    static PriorityQueue<info> pq = new PriorityQueue<>();	//강연 정보 저장할 우선순위 큐
    static boolean[] check;	//강연 진행 확인 배열
    static int n, max = -1, answer = 0;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        //강연에 대한 정보 우선순위 큐에 저장
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine()," ");
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            max = Math.max(max, d);		//제한일 최대값
            pq.add(new info(p, d));	//우선순위 큐에 저장
        }
        //최대값 만큼 배열 설정
        check = new boolean[max+1];
        //우선순위 큐에 정보들 탐색
        while(!pq.isEmpty()){
            info cur = pq.poll();
            //해당 강연 가능한지 탐색
            for(int i=cur.d-1;i>=0;i--){
                if(!check[i]){		//가능한 날짜 존재시
                    check[i] = true;	//해당 날짜 강연 진행
                    answer += cur.p;	//금액 증가
                    break;		//탐색 종료
                }
            }
        }
        bw.write(answer + "");	//총 금액 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}