본문 바로가기
백준

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

by 열정적인 이찬형 2022. 11. 25.

문제 링크

 

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net


주의사항

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

댓글