[백준, Java] 7983번, 내일 할거야(그리디)

문제 링크

7983번: 내일 할거야

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. n개의 과제가 존재하며, 각 과제는 d일이 걸리고 t일 안에 해결해야 합니다.

2. 내일부터 최대한 놀고싶으며, 과제는 무조건 모두 해야 합니다.

3. 내일(1일)부터 연속으로 놀 수 있는 지를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 숙제를 마감시간에 최대한 가깝게 진행하여 초기에 놀 수 있는 시간을 탐색합니다.

 

3. 탐색을 통해 초기에 놀 수 있는 연속된 일 수를 결과로 출력합니다.

 

 

내일부터 노는 최대 요일 수(그리디)

 

내일(1일)부터 최대한 놀기 위해서는 숙제를 최대한 뒤로 미루어서 시간을 보장해야 합니다.

 

즉, d, t가 주어졌을 때 해당 숙제를 해결하는 시간은 t에 만족하는 가장 가까운 일부터 숙제를 진행해야 한다는 것입니다.

 

예를 들어,

 

d : 13, t : 5일 때

 

최대한 숙제를 늦게 하기 위해서 9 ~ 13일 동안 숙제를 진행해야 한다는 것입니다.

 

위 같이 n개에 대한 숙제를 기준으로 마감기한(t)가 가장 큰 값부터 순차적으로 숙제를 최대한 늦게 진행하여 1일부터 숙제를 진행하지 않도록 하였을 때 연속된 일이 최대 놀 수 있는 연속된 일 수라는 것을 확인할 수 있습니다.

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

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

 

숙제 정보

 

	d	t
숙제1	2	8
숙제2	1	13
숙제3	3	10

 

 

2. 숙제를 마감시간에 최대한 가깝게 진행하여 초기에 놀 수 있는 시간을 탐색합니다.

 

숙제 마감시간이 가장 큰 값부터 순차적으로 마감일에 가깝게 작업을 진행해야 하기 때문에 마감기간(t)를 기준으로 정렬하겠습니다.

 

	d	t
숙제2	1	13
숙제3	3	10
숙제1	2	8

 

최대 마감 시간 : 13일

 

13일 기준으로 각 숙제들을 최대한 늦게 수행

 

[X : 놀기, O : 숙제]

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13
X	X	X	X	X	X	X	X	X	X	X	X	X	X

 

 

★ 마감 시간이 큰 숙제부터 순차적으로 진행합니다.

 

 

숙제2(d = 1, t = 13) 진행

[X : 놀기, O : 숙제]

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13
X	X	X	X	X	X	X	X	X	X	X	X	X	O

숙제3(d = 3, t = 10) 진행

[X : 놀기, O : 숙제]

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13
X	X	X	X	X	X	X	X	O	O	O	X	X	O

숙제1(d = 2, t = 8) 진행

[X : 놀기, O : 숙제]

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13
X	X	X	X	X	X	O	O	O	O	O	X	X	O

→ 8일에 이미 숙제를 하기 때문에 7일부터 숙제를 진행하게 됩니다.

 

 

 

모든 숙제를 진행하였으며, 이 상황에서 1일부터 연속하여 노는 최대 일 수를 구할 수 있습니다.

[X : 놀기, O : 숙제]

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13
X	X	X	X	X	X	O	O	O	O	O	X	X	O

→ 1 ~ 5일까지 놀 수 있습니다.

 

 

3. 탐색을 통해 초기에 놀 수 있는 연속된 일 수를 결과로 출력합니다.

내일(1일)부터 노는 일 : 5일(1 ~ 5)

 

5 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 숙제 정보를 띄어쓰기 기준 나누었습니다.
• TreeMap<>을 통해서 마감기한 기준 내림차순으로 정렬하였습니다.
• 마감기한 내림차순으로 숙제를 순차적으로 진행하여 내일부터 연속하여 놀 수 있는 요일을 탐색합니다.
• 탐색을 통해 얻은 연속된 요일 수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.*;


public class Main {
    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;
        //숙제 마감 기한 기준 내림차순 정렬되는 맵
        Map<Integer, Integer> workMap = new TreeMap<>(Comparator.reverseOrder());
        int curTime = 0;
        //숙제 정보 저장
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine()," ");
            int d = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            //최대 마감일 설정
            curTime = Math.max(t, curTime);
            workMap.put(t, workMap.getOrDefault(t, 0)+d);
        }
        //마감 기한 내림차순 숙제 진행
        for(int key : workMap.keySet()){
            if(key < curTime){
                curTime = key;
            }
            curTime -= workMap.get(key);
        }
        //1일부터 연속되어 놀 수 있는 최대 일 BufferedWriter 저장
        bw.write(String.valueOf(curTime));
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}