[JAVA] 백준 13904 과제 - 골드3

 

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

13904번: 과제

 

어떻게 풀어야할지 감도 못잡았던 문제다ㅠㅠㅠ

점수순으로 정렬을 해야할 것 같은데, 그 뒤로는 어떻게 풀어야할지 아이디어가 떠오르지 않았다. 

그리디도 아닌 것 같아 그냥 백트래킹으로 구현해봤더니 당연히 시간초과가 발생했다. 결국 풀이 방법을 구글링해봤다

 

 

이 문제는 그리디였다....(허무)

날짜를 내림차순으로 내려가며 뽑을 수 있는 최대의 이익을 뽑으면 된다고 한다. 풀이는 다음과 같다

 

그리디 풀이

class Task {
  int day;
  int score;

  public Task(int day, int score) {
    this.day = day;
    this.score = score;
  }
}

class Main {
  
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int taskCnt = Integer.parseInt(br.readLine());
    List<Task> list = new ArrayList<>();
    
    int result = 0;
    int maxRemainingDay = 0;

    StringTokenizer st;
    for (int t =0; t<taskCnt; t++) {
      st = new StringTokenizer(br.readLine());
      int remainingDay = Integer.parseInt(st.nextToken());
      int score = Integer.parseInt(st.nextToken());
      list.add(new Task(remainingDay, score));

      if (maxRemainingDay < remainingDay)
        maxRemainingDay = remainingDay;
    }

    list.sort(new Comparator<Task>() {
      @Override
      public int compare(Task o1, Task o2) {
        if (o2.score == o1.score)
          return o2.day - o1.day;
        else
          return o2.score - o1.score;
      }
    });

    boolean[] days = new boolean[maxRemainingDay+1];

    for (int d = days.length-1; d>=1; d--) {
      for (Task t: list) {
        if (t.day >= d) {
          result += t.score;
          list.remove(t);
          break;
        }
      }
    }

    System.out.println(result);
  }
}

1. 마감일과 점수를 저장할 Task객체를 만든다
2. Task객체들을 taskList에 저장한다
3. list를 점수 내림차순으로 정렬한다
4. 일수를 저장할 days배열을 만든다. 크기는 마감일의 최댓값+1 이고, 0번째 인덱스는 사용하지 않을 것이다
5. days배열을 마지막 인덱스부터 1까지 돌면서 해당 날짜에 얻을 수 있는 최대 이익 task를 taskList에서 찾는다
   • 찾으면 taskList에서 삭제해주고 점수를 result에 더한다
6. result를 출력한다