[Java] 백준 2109 순회강연 - 골드3

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

2109번: 순회강연

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;


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

    int universityCnt = Integer.parseInt(br.readLine());
    int[][] arr = new int[universityCnt][2];
    int maxDay = -1;

    for (int i=0; i<universityCnt; i++) {
      String[] tmp = br.readLine().split(" ");
      arr[i][0] = Integer.parseInt(tmp[0]); //강연료
      arr[i][1] = Integer.parseInt(tmp[1]); //가야하는 날
      if (arr[i][1] > maxDay)
        maxDay = arr[i][1];
    }

    Arrays.sort(arr, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0])
          return o2[1] - o1[1];

        return o2[0] - o1[0];
      }
    });

    boolean[] day = new boolean[maxDay+1];
    int result = 0;

    for (int[] one: arr) {
      int money = one[0];
      int pDay = one[1];

      while (pDay >0 && day[pDay] == true )
        pDay--;

      if (pDay != 0) {
        day[pDay] = true;
        result += money;
      }
    }

    System.out.println(result);
  }
}

• 메모리를 조금 줄이려고 maxDay를 저장해줬다. 
• 대학마다 강연료와 가야하는 날을 arr 2차원 배열에 저장한다
• arr배열을 강연료 내림차순으로 정렬하고, 강연료가 같다면 가야하는 날이 긴 것이 먼저오도록 내림차순 정렬한다. (그냥 인덱스 0으로 내림차순 정렬하고, 값이 같으면 인덱스 1을 내림차순으로 정렬하는 것)
• day에 강연이 있는 날을 boolean으로 표시한다
• 모든 arr의 값들을 for문으로 돈다
  • 내림차순 정렬된 arr배열에서 강연료가 젤 높은 것을 뽑고, 날짜에 강연이 가능한 지 확인한다.
    • 만약 강연이 가능하다면 day[해당 날짜] 를 true로 만들고 result에 강연료를 더한다
    • 만약 강연이 불가능하다면 그 전날 가능한지 계속 확인하고, 가능한 날이 있으면 day[해당 날짜]를 true로 만들고 result에 강연료를 더한다