BOJ 13904 과제
https://www.acmicpc.net/problem/13904
시간 1초, 메모리 256MB
input :
- N (1 ≤ N ≤ 1,000)
- d (1 ≤ d ≤ 1,000) w (1 ≤ w ≤ 100) [d는 과제 마감일까지 남은 일수 w는 과제의 점수]
output :
- 점수의 최댓값을 출력
조건 :
- 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다.
- 마감일이 지난 과제는 점수를 받을 수 없다.
하루가 지날 때 마다 무엇을 해야할 지 판단을 해야 하나 싶었는데, 그럴 경우 날짜 마다 가장 큰 값을 고르다 보면 다른 값을 놓치는 경우가 발생할 수 있다.
다른 방법들 중, 하루하루 지나는 것이 아닌 | 현재 부터 마감일 까지의 과제 제출 계획을 세우는 방식으로 하는 것이 좋을 것 같다.
과제 마감일 까지 남은 일 수 중 가장 큰 값은 1000이다.
1000짜리 배열을 만들어 각 날 짜마다 해야 할 과제의 점수를 넣는다.
그리고 마지막에 이 값을 더하도록 하자.
예제.
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
이것을 점수의 내림차순으로 정렬을 한 후에.
각 값을 할 날짜가 존재하는지 확인을 해야 한다. 자신이 하려는 날짜에 이미 다른 과제가 있다면 날짜 - 1을 해가면서 확인을 하다가 이 값이 -1 즉 0보다 작아지면 포기 한다.
이를 while문으로 나타냈다.
그리고 중간에 data[cnt] != 0을 조건으로 거는 바람에 에러가 발생했는데 이를 방지하기 위해 cnt >= 0을 먼저 걸리게 한다.
그러면 연산자 우선순위로 인해 앞에 거를 먼저 판별 하기에 상관이 없어진다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
class Problem implements Comparable<Problem>{
int day, score;
public Problem(int day, int score){
this.day = day;
this.score = score;
}
@Override
public int compareTo(Problem o){
return o.score - this.score;
}
}
public class BOJ_13904_assignment {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] data = new int[1000];
static ArrayList<Problem> problem = new ArrayList<>();
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++){
String[] temp = br.readLine().split(" ");
problem.add(new Problem(Integer.parseInt(temp[0]), Integer.parseInt(temp[1])));
}
Collections.sort(problem);
for (Problem item : problem){
int cnt = item.day - 1;
while (cnt >= 0 && data[cnt] != 0) {
cnt--;
}
if (cnt < 0)
continue;
data[cnt] = item.score;
}
int sum = 0;
for (Integer item : data)
sum += item;
System.out.println(sum);
}
}
Author And Source
이 문제에 관하여(BOJ 13904 과제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-13904-과제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)