백준

[백준/JAVA] 2109번: 순회강연

찌끄랭이 2023. 2. 20. 14:45

문제 보러가기

 

2109번: 순회강연

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다.

www.acmicpc.net

[문제 풀이]

예제의 마감일을 수정하여 대학에서 제시한 강연료 p를 기준으로 내림차순 하였다.

제시한 값 마감일
100 2
50 5
20 1
10 3
8 2
5 6
2 1

첫번째 제시한 값은 100이고 마감일은 2일이다. 즉, 1일 혹은 2일에 강연을 하면 된다.

두번째 제시한 값은 50이고 마감일은 5일이다. 1일/2일/3일/4일/5일에 강연을 하면 된다.

같은 방식으로 마지막으로 제시한 값 2이고 마감일이 1일인 경우가 있다.

 

강연료를 내림차순으로 정렬했기에 우리가 결정해야할 것은 몇 일에 강연을 할지 정하는 것이다.

여기서 몇 일에 얼마의 강연료를 주는 강의를 할지 저장하는 배열을 생성했다.

날짜 1 2 3 4 5 6
강연료 0 100 0 0 0 0

첫번째로 강연료 100을 주는 강의를 1일부터 2일까지 선정해서 저장하였다.

 

날짜 1 2 3 4 5 6
강연료 0 100 0 0 50 0

다음으로 강연료를 50을 주는 강의를 1일부터 5일까지 선정해서 저장하였다.

 

여기서 눈여겨서 봐야하는 것은 1일부터 마감일까지의 배열안에서 선정해야하는 것이다.

같은 방법으로 배열을 채워본다면

날짜 1 2 3 4 5 6
강연료 20 100 0 0 50 0
날짜 1 2 3 4 5 6
강연료 20 100 10 0 50 0

여기서 강연료가 8이고 마감일이 2일인 강의는 1일과 2일에 있는 강연료 20과 100보다 낮기때문에 무시한다.

날짜 1 2 3 4 5 6
강연료 20 100 10 0 50 5

이렇게 채워진 배열의 합이 우리가 받을 수 있는 최대의 강연료이다.

 

[코드]

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        
        int[][] numbers = new int[N][2];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            if (d > max) max = d;
            numbers[i][0] = d;
            numbers[i][1] = p;
        }

        Arrays.sort(numbers, (o1, o2) -> o2[1] - o1[1]); //강연료를 기준으로 내림차순

        if (N == 0) System.out.println(0);
        else {
            int[] days = new int[max + 1]; //각 요일마다 강의를 채울 배열 
            int result = 0;
            for (int[] number : numbers) {
                int index = 0;
                int day = number[0];
                int value = number[1];

                for (int j = 1; j <= day; j++) {
                    if (days[j] < value) { //1일부터 마감일까지 가장 작은 강연료를 가진 배열에 채운다.
                        index = j;
                    }
                }

                if (index != 0) {
                    result += value; // 배열을 모두 더할 필요 없이, 이 조건에서 강연료를 정답으로서 추가해도 무방하다.
                    days[index] = value;
                }
            }
            System.out.println(result);
        }
    }
}
저작자표시 (새창열림)