[백준] 알고리즘 분류(그리디 알고리즘,JAVA)13904번, 과제

문제 링크

13904번: 과제

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 하루에 과제를 1개만 끝낼 수 있습니다.

2. 과제마다 마감일 및 끝냈을 때 점수가 존재합니다.

3. 주어진 과제를 임의의 순서로 해결할 때 얻을 수 있는 최대 점수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 점수 기준 내림차순 정렬되도록 우선순위 큐에 저장한 뒤, 숙제를 해결과정을 탐색합니다.

 

3. 탐색이 끝난 뒤 얻은 점수의 합을 결과로 출력합니다.

 

 

숙제 해결과정 탐색

※우선순위 큐에 내림차순으로 정렬되어있는 상태에서 탐색 진행!

※Why 내림차순? : 최대 점수를 얻기 위해서 최대한 점수가 높은 숙제를 끝내야 하기 때문입니다. 

 

 

내림차순으로 각 숙제들을 받았을 때

 

마감일에서 가장 가까운 곳에 해당 숙제를 해결한다고 배정합니다.

 

예를 들어

 

2가지 숙제에 대한 정보를 탐색할 때

 

4 60 : 4일에 해당 숙제를 해결한다.

 

4 50 : 4일에는 숙제를 해결하니까 3일에 숙제를 해결합니다.

 

 

해당 일에 숙제를 해결했는지 확인하기 위해서 boolean[]을 사용하여 확인하였습니다.

 

예제입력 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

 

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();
    }
}