[백준 / BOJ 2109] 순회강연

 

https://www.acmicpc.net/problem/2109

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값이 주어진다.

 

출력

---

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

 

풀이

---

정렬과 브루트포스 문제!

pay와 day를 저장할 lecture class를 만들었다. 이 lecture은 금액이 큰 순서로, 같으면 날짜가 작은 순서로 정렬되도록 했다.

boolean 배열로 lecture의 날짜안에 강연이 가능한지 확인했다.

 

‼️ 처음에는 문제를 잘못 이해해서.... d의 의미가 그 날짜에 강연이 가능한가? 라는 것인지 알았따아.. 

그게 아니라 d일 안에 강연이 가능한가!!  이것이 중요한 POINT 

 

코드

---

처음에 문제를 잘못이해해서 틀린 코드....😭

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;


public class Main{
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        int n = Integer.parseInt(br.readLine());
        Map<Integer, Integer> univ = new HashMap<>();

        while(n-- > 0){
            stringTokenizer = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(stringTokenizer.nextToken());
            int d = Integer.parseInt(stringTokenizer.nextToken());

            if(univ.containsKey(d)){
                int p1 = univ.get(d);
                if(p1 < p)
                    univ.put(d, p);
                else
                    continue;
            }
            
            else
                univ.put(d, p);
        }

        long answer = 0;
        Set<Integer> kSet = univ.keySet();
        for(int k : kSet){
            answer += univ.get(k);
        }

        System.out.println(answer);

    }
}

 

여러번의 시도끝에 맞은 코드;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;


public class Main_BOJ_2109_순회강연{

    static class lecture implements Comparable<lecture>{
        int pay;
        int day;

        lecture(int pay, int day){
            this.pay = pay;
            this.day = day;
        }

        @Override
        public int compareTo(lecture o) {
            // TODO Auto-generated method stub
            int result = o.pay - this.pay;

            if(result == 0)
                result = this.day - o.day;

            return result;
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

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

        boolean[] days = new boolean[10001];
        List<lecture> list = new ArrayList<>();
        while(n-- > 0){
            stringTokenizer = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(stringTokenizer.nextToken());
            int d = Integer.parseInt(stringTokenizer.nextToken());

            list.add(new lecture(p, d));
        }

        Collections.sort(list);

        int answer = 0;
        for(lecture l : list){
            // lecture를 금액 내림차순 || 날짜 오름차순으로 했기때문에, 역순으로 하지않으면 나중에 나오는 day가 작은 강연은 들어갈 수 없음
            for(int j = l.day ; j > 0 ; j--){
                if(!days[j]){
                    days[j] = true;
                    answer += l.pay;
                    break;
                }
            }
        }
        System.out.println(answer);
    }
}