[자바] 백준 13904번: 과제

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

13904번: 과제

 

점수가 높은 순으로 과제들을 정렬한다.

과제를 하나씩 뽑는다.

가능한 한 마감일에 가까운 날짜에 (최대한 늦게) 과제를 해결하고 점수를 추가한다

만약 마감일 내에 스케줄이 꽉 차 있으면 해당 과제는 포기한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P13904 {

	static class HW {
		int d;
		int w;

		public HW(int d, int w) {
			this.d = d;
			this.w = w;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		StringTokenizer st;

		PriorityQueue<HW> pq = new PriorityQueue<>(new Comparator<HW>() {
			@Override
			public int compare(HW o2, HW o1) {
				if (o1.w == o2.w)
					return o1.d - o2.d;
				return o1.w - o2.w;
			}
		});

		boolean[] schedule = new boolean[1001];
		for (int i = 0; i < 1001; i++) {
			schedule[i] = false;
		}

		int result = 0;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			pq.add(new HW(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}

		while (!pq.isEmpty()) {
			HW now = pq.poll();
			int deadline = now.d;
			while (schedule[deadline] == true) {
				deadline--;
			}
			if (deadline == 0)
				continue;
			result += now.w;
			schedule[deadline] = true;
		}

		System.out.println(result);

	}

}

과제들을 HW클래스로 나타내고,

HW객체를 담는 우선순위큐 pq를 생성했다.

pq는 HW의 w(점수)를 기준으로 내림차순으로 정렬된다.

 

스케쥴을 나타낼 boolean schedule[1001]을 생성했다.

하루에 하나의 과제를 할 수 있으므로, 

과제를 한 날은 true로, 과제를 안 한 날은 false로 기록할 수 있게 했다.

 

마감까지 남은 시간이 0인 과제는 없으므로 

schedule[0]은 항상 false이다.

deadline을 1씩 감소시키며 과제를 해결할 수 있는 날짜를 찾는데,

과제를 해결할 수 있는 날이 없는경우 deadline은 0이 된다(schedule[0]은 항상 false이므로)

이 경우에는 과제를 포기하고 넘긴다.

과제를 해결할 수 있는 날이 있는 경우는 해당 날짜에 schedule값을 true로 변경하고 점수를 추가한다.