백준 No.27112 시간 외 근무 멈춰! - JAVA

문제 

오늘도 여러 체계의 개발 임무를 열심히 수행 중인 준민이에게 갑자기 새로운 개발프로젝트가 들어왔다. 해당 개발 프로젝트는 총 N개의 작업으로 이루어져 있으며, 각 작업은 t의 근무일이 필요하며 개발 프로젝트가 시작한 이후 d일이 지나기 전에 끝내야 한다. 그러나 평시 근무만으로는 모든 N개의 작업을 시간 내에 끝내기 힘들어 보였던 준민이는 개인 정비시간을 포기하며 시간 외 근무를 하고자 한다.

개발 프로젝트는 월요일부터 시작하며, 평시 근무는 월요일부터 금요일까지만 진행한다. 시간 외 근무는 요일과 관계없이 매일 최대 한 번씩만 진행할 수 있으며, 시간 외 근무를 1회 진행하면 1일치 업무를 끝마칠 수 있다.

 

준민이는 이를 토대로 효과적인 일정을 짜고 싶었지만, 이미 프로젝트로 너무 바빠진 준민이는 일정을 짤 시간조차 없는 상태이다. 바쁜 준민이를 위해, 모든 작업을 마감 기한 전까지 끝내고자 할 때 하는 최소 시간 위 근무 일 수를 알려주자.

5
5 4
6 2
2 1
9 1
10 3

 

 

어려웠던 점 

처음에 당연히 정렬하고 푸는 문제인 거 같아 마감 기한이 짧은 순으로 정렬하기 위헤 우선순위 큐를 사용해 받아 사용했는데 하... 계속 틀렸다.... 그래서 정말 계속 검색했는데 자료가 없어서 찾다가 마침내 주말을 뺴고 구하는 식을 보게되어 추가했더니 맞았따......

 

풀이

 

int date = job.d (마감기한);

date -= (job.d/7)*2; 하면 주말 값을 빼준다. 그러면 온전히 평일로 변함.... 대박

 

흐름을 보면 당연하게도 우선순위 큐가 빌떄까지 순회하도록 while문을 돌린다.

해당 과정에서 변수를 하나 만들어 위처럼 주말을 제외한 날을 구해준 다음에 

workDay += job.t(처리하는데 걸리는 날짜) 를 계속해줘야한다. 

 

if(workDay > limit) --> 해당 기한내에 못한다는 거임 추가근무(야근)필요

          result += workDay - limit; //해야하는데 걸리는 날짜에서 평일을 빼면 추가근무를 해야하는 날짜가 나온다.

          workDay = limit;  //평일에 처리한 만큼을 담아준다. 

}

 

if(result > job.d){ //마감기한보다 처리할게 더 많다면  

      result = -1;

     break;

}

 

package Practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ27112 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        PriorityQueue<Job> jobs = new PriorityQueue<>(((o1, o2) -> o1.d - o2.d));

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            jobs.add(new Job(d, t));
        }

        int result =0 ;
        int limit = 0;
        int workDay = 0;

        while (!jobs.isEmpty()){

            Job job = jobs.poll();

            limit = job.d;
            limit -= (job.d/7)*2;  //평일

            if(job.d % 7 == 6) limit--;

            workDay += job.t;   //해야할 것추가

            if(workDay > limit){    //해야할게 기간보다 많을 겨우
                result += workDay - limit;  //업무를 처리하고 남은 것들을 result에 추가함

                workDay = limit;    //처리한 것들은 workDay에 담아둬야함
            }

            if(result > job.d){ //마감기한보다 처리할게 더 많다면  
                result = -1;
                break;
            }

        }
        System.out.println(result);



    }

    static class Job{
        int d; //마감기한
        int t; //걸리는시간

        public Job(int d,int t){
            this.d = d;
            this.t = t;
        }
    }
}