백준과제 #13904 (Greedy – Gold 3), (Umtang 개발 블로그) Java
안녕하세요. 개발자 움탱입니다.
이 게시물은 알고리즘을 배우면서 학습한 내용을 문서화하기 위한 것입니다.
그래서 저는 각 설명을 편안하게 저널링하고 짧은 형식으로 기록하려고 노력합니다.
더 좋은 방법이 있거나 잘 이해되지 않는 부분이 있으면 알려주시면 감사하겠습니다.
좋은 하루 되세요:)
개념이 한눈에 이해되고 공부하기 쉽기 때문에 욕심쟁이 문제가 떠오른다.
하지만 가볍게 받아들일 알고리즘은 아니라고 생각합니다.
매 순간 올바른 방법을 선택해야 하고, 정렬이 필요한 경우 올바른 방법으로 정렬해야 합니다.
은과 금 문제를 해결한 후 Silver는 문제를 해결하기 위해 추측에 불과하다고 생각합니다. 최근에 나는 “똥이야”에 좌절하고 있습니다 …
태클을 많이 하면 좋아지나요?
첫째, 단기간에 많은 문제를 푸는 것이 중요해 보인다.
질문
웅찬이는 할 일이 많다. 하루에 하나의 작업완료할 수 있습니다 각 과제에는 마감일이 있으므로 모든 과제를 완료하지 못할 수도 있습니다. 각 과제에는 완료 시 획득할 수 있는 학점이 있지만 마감일이 지난 과제에 대해서는 학점이 부여되지 않습니다.
시옹 칸 가장 많은 점수를 얻기 위해 작업을 수행하고 싶습니다. 웅찬이를 도와주면 얻을 수 있다 최고 점수구하다
입력하다
첫 번째 줄은 정수 N(1 ≤ N ≤ 1,000)을 제공합니다.
다음 N 라인은 각각 두 개의 정수 d(1 ≤ d ≤ 1,000) 및 w(1 ≤ w ≤ 100)를 제공합니다. d는 과제 마감일까지 남은 일수이고 w는 과제의 점수입니다.
인쇄
획득할 수 있는 최대 점수를 출력합니다.
예
힌트
예에서 5, 4, 2, 1, 7 작업을 순서대로 완료하고 3, 6 작업을 포기하면 185점을 얻을 수 있습니다.
알고리즘 분류
- 데이터 구조
- 그리디 알고리즘
- 유형
- 우선순위 큐
문제 설명
현재 문제는 Xiongcan이 기한 내에 다양한 과제를 완료해야 하고 기한 내에 모든 작업을 완료하지 못할 수도 있다는 것입니다.
이때, 마감일과 점수가 다른 과제에 대해 어떤 순서로 가장 높은 점수를 얻는 방법예.
논평
이 질문을 보고 처음 든 생각은 정말 저에게 해당된다면 순서를 어떻게 정할까 였습니다.
나는 단지 놀고 대학에 가지 않습니까? 내가 그런 짓을 했나요? 그러고 보니 대학에서 숙제를 최대한 미루는 데 사용되는 말입니다.
그래도, 가장 높은 점수 먼저그 다음에 그 기간 동안 최대한 미루고, 급한 일은 먼저 하도록 하세요. 그랬던 것 같아요.
즉, 이 문장에는 질문의 핵심이 모두 포함되어 있습니다.
- 가능한 점수 오름차순 첫 번째(점수 내림차순)
- 기한 종료 시 높은 순서로 완료하도록 노력(마감 기한 종료 시 완료해야 하는 작업이 있는 경우 기한 전날 완료)
기한을 나타내기 위해 부울 배열을 사용했습니다.
해설(보충, 생략 가능)
여기에서 1번은 예라고 하고 완료할 수 있는데 2번은 왜 마감시간 안에 해야 하는지 마감시간 끝에 해야 할 일이 있다면 전날에 설정하려면? 전날 끝내야 할 숙제가 있지 않을까요?생각할 수 있다
생각해보자
우선 마감일 전에 가능한 한 늦게 과제를 끝내려고 하는 이유는 무엇입니까?
(A(2일) > B(1일) 과제 점수로 가정)
우선 순위가 가장 높은 작업이 가장 높은 점수이므로 반드시 수행해야 합니다.
그러나 당신이 작업 A를 첫날에 끝내고 마감일을 넘기지 않는다고 가정해 봅시다. 음, 다음으로 높은 수준의 작업 B가 1일 만기인 경우, 만기일까지 작업 A를 연기했다면 A+B를 받았겠지만 첫날 A를 한 것입니다. A등급만 받을 수 있습니다. 따라서 최대한 연기해야 한다.
(A(2일) > B(2일) > C(1일) 숙제 점수로 가정)
그렇다면 마감일까지 완료해야 할 작업이 있는 경우 마감일 하루 전에 설정될 수 있는 이유는 무엇입니까?
여기서 중요한 것은 C의 과제 성적이 B보다 높다는 것입니다. 그래서 A는 2일, B는 2일, A가 있으니 1일에 가더라도 C를 하는 것보다 B를 하는 것이 더 중요하다.
코드
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static void main(String() args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
int()() arr = new int(T)(2);
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
arr(i)(0) = d;
arr(i)(1) = w;
}
Arrays.sort(arr, ((x, y) -> y(1) - x(1)));
boolean() ck = new boolean(1001);
int point = 0;
for (int i = 0; i < arr.length; i++) {
int d = arr(i)(0);
int w = arr(i)(1);
for (int j = d; j > 0; j --) {
if (!ck(j)) {
point += w;
ck(j) = true;
break;
}
}
}
bw.write(point+ "\n");
bw.flush();
bw.close();
br.close();
}
}