백준 13904번 과제 [JAVA]

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

 

입력

첫 줄에 정수 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.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_BJ_13904_과제 {
    static class info implements Comparable<info>{
        int d, w;
 
        public info(int d, int w) {
            this.d = d;
            this.w = w;
        }
    
        @Override
        public int compareTo(info o) {
            return (this.w-o.w) * -1;
        }
        
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        ArrayList<info> list = new ArrayList<>();
        
        int N = Integer.parseInt(br.readLine());
        int [] homework = new int[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());
            list.add(new info(d,w));
        }
        
        Collections.sort(list);
        
        for(int i=0;i<list.size();i++) {
            int d = list.get(i).d;
            int w = list.get(i).w;
            
            if(homework[d]==0) homework[d]= w;
            else {
                while(homework[d]!=0) d--;
                if(d!=0) homework[d] = w;
            }
        }
        int sum=0;
        for(int i=1;i<homework.length;i++) sum+=homework[i];
        
        System.out.println(sum);
        
    }
 
}

 

풀이 방법

과제 점수의 최댓값을 구하는 문제였습니다. 먼저 하루에 한 과제를 끝낼 수 있고, 마감일이 지난 과제는 점수를 받을 수 없으므로 과제 점수를 오름차순으로 정렬해주었습니다. 그러고 난 뒤, 과제점수를 기준으로 만약 마감일인 인덱스가 0인 경우에는 과제를 해결할 수 있으므로 배열에 넣고, 인덱스가 0이 아닌 경우에는 그 날 해야 하는 과제가 있으므로 마감일 변수인 d를 --해줌으로써 과제를 마감일 전에 할 수 있도록 해주었습니다. 마지막으로 sum변수에 해당하는 과제 점수를 더해 출력해주었습니다.