https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
문제
웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.
웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.
입력
첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.
다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.
출력
얻을 수 있는 점수의 최댓값을 출력한다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
int arr[][] = new int[n][2];
int maxday = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
if (maxday < arr[i][0]) maxday = arr[i][0];
}
int sum = 0;
int idx;
int max;
for (int i = maxday; i > 0; i--) {
max = 0;
idx = -1;
for (int j = 0; j < n; j++) {
if(i <= arr[j][0]) {
if(max < arr[j][1]) {
max = arr[j][1];
idx = j;
}
}
}
if(idx != -1) {
sum += max;
arr[idx][0] = -1;
}
}
System.out.println(sum);
}
}
해결방법
하루에 하나의 과제만 끝낼 수 있고 마감일이 지난 과제는 점수를 얻지 못한다. 이때, 점수의 최댓값을 구하는 문제이다.
처음부터 탐색을 하면 경우의 수가 너무 많다. 1일차에 택할 수 있는 과제가 많기 때문이다.
고로, 뒤에서부터 탐색을 하였다. 그러면 해당 일(M)에 택할 수 있는 과제의 수는 [M <= 과제 마감일] 조건을 만족하는 과제만 해당되기 때문이다. 이 중에 가장 점수가 큰 과제를 수행하면 자연스럽게 점수의 최댓값을 구할 수 있다.
예제 1을 예시로 들면
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
일자 | 가능한 과제 | 최적의 과제 |
6 | (6, 5) | (6, 5) |
5 | X | X |
4 | (4, 10), (4, 40), (4, 60) | (4, 60) |
3 | (3, 30), (4, 10), (4, 40) | (4, 40) |
2 | (2, 50), (3, 30), (4, 10) | (2, 50) |
1 | (1, 20), (3, 30), (4, 10) | (3, 30) |
'알고리즘 > 백준' 카테고리의 다른 글
1374번 : 강의실 (0) | 2023.08.04 |
---|---|
10775번 : 공항 (0) | 2023.08.03 |
12904번 : A와 B (0) | 2023.08.02 |
2212번 : 센서 (0) | 2023.08.02 |
19539번 : 사과나무 (0) | 2023.07.31 |