문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 하루에 과제를 1개만 끝낼 수 있습니다.
2. 과제마다 마감일 및 끝냈을 때 점수가 존재합니다.
3. 주어진 과제를 임의의 순서로 해결할 때 얻을 수 있는 최대 점수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 점수 기준 내림차순 정렬되도록 우선순위 큐에 저장한 뒤, 숙제를 해결과정을 탐색합니다.
3. 탐색이 끝난 뒤 얻은 점수의 합을 결과로 출력합니다.
숙제 해결과정 탐색
※우선순위 큐에 내림차순으로 정렬되어있는 상태에서 탐색 진행!
※Why 내림차순? : 최대 점수를 얻기 위해서 최대한 점수가 높은 숙제를 끝내야 하기 때문입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N = 7
숙제 정보
숙제 1 | 숙제 2 | 숙제 3 | 숙제 4 | 숙제 5 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 4 | 1 | 2 | 3 | 4 | 6 |
점수 | 60 | 40 | 20 | 50 | 30 | 10 | 5 |
2. 점수 기준 내림차순 정렬되도록 우선순위 큐에 저장한 뒤, 숙제를 해결과정을 탐색합니다.
내림차순 정렬되도록 우선순위 큐에 저장!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 1 : 4일에 숙제 수행!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 4 : 2일에 숙제 수행!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 2 : 4일에는 숙제 1이 수행되기 때문에 3일에 숙제 수행!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 5 : 3일에는 숙제 2, 2일에는 숙제 4가 수행되기 때문에 1일에 숙제 수행!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 3 : 1일에 이미 숙제를 수행하고 더 이상 줄어들 날이 없으니 수행 불가능!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 6 : 1~4까지 모두 숙제를 수행해서 더 이상 줄어들 날이 없으니 수행 불가능!
숙제 1 | 숙제 4 | 숙제 2 | 숙제 5 | 숙제 3 | 숙제 6 | 숙제 7 | |
마감일 | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
점수 | 60 | 50 | 40 | 30 | 20 | 10 | 5 |
숙제 7 : 6일에 숙제 수행!
3. 탐색이 끝난 뒤 얻은 점수의 합을 결과로 출력합니다.
숙제를 수행한 점수들을 모두 더합니다.
60(숙제1) + 50(숙제4) + 40(숙제2) + 30(숙제5) + 5(숙제7) = 185
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 숙제의 정보를 띄어쓰기 기준 나누었습니다.
- 숙제의 정보에서 점수 기준 내림차순으로 정렬되도록 PriorityQueue에 저장하였습니다.
- PriorityQueue 저장된 숙제 정보를 탐색하여 각 날짜에 수행할 숙제들을 배정합니다.
- 배정이 성공한 숙제들의 점수의 합을 결과로 BufferedWriter에 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
import java.io.*;
import java.util.*;
public class Main{
//숙제 정보 관련 클래스
static class info implements Comparable<info>{
int day, score;
public info(int day, int score){
this.day = day;
this.score = score;
}
//숙제 정보에서 점수 기준 내림차순 정렬
@Override
public int compareTo(info o) {
return o.score - this.score;
}
}
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
//숙제 정보 저장할 우선순위 큐
PriorityQueue<info> pq = new PriorityQueue<>();
boolean[] check = new boolean[1001]; //숙제 수행 여부 확인 배열
//숙제 정보 저장
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
int d = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
pq.add(new info(d, w));
}
int answer = 0;
//숙제 해결과정 탐색
while(!pq.isEmpty()){
info cur = pq.poll();
//마감일에 숙제를 수행!
if(!check[cur.day]){
answer += cur.score;
check[cur.day] = true;
}else{
//마감일에서 가장 가까운 날에 숙제를 수행!
for(int j=cur.day-1;j>=1;j--){
if(!check[j]){
answer += cur.score;
check[j] = true;
break;
}
}
}
}
bw.write(answer + ""); //얻은 점수의 합 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
}
'백준' 카테고리의 다른 글
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)14720번, 우유 축제 (0) | 2022.11.26 |
---|---|
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)14659번, 한조서열정리하고옴ㅋㅋ (0) | 2022.11.26 |
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)11501번, 주식 (2) | 2022.11.24 |
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1041번, 주사위 (0) | 2022.11.23 |
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2012번, 등수 매기기 (0) | 2022.11.22 |
댓글