백준(BOJ) 27112 시간외 근무 멈춰!!!

https://www.acmicpc.net/problem/27112

 

문제의 특성!

-"주말에는 정규근무를 할수 없다." 이러한 조악한 조건들이 들어가면 문제가 지저분해 진다. 다만, 단순히 지저분해 진다고 해서 그 지저분한 것을 어떻게 구현하나로 방향을 잡지 말고 그 조악한 것을 문제에서 주워진 조건을 변형하고 어떻게 상쇄시켜버릴지, 없애버릴지 생각해 내는 것은 참 훌륭한 것같다. 실제 예를들면 아래와 같다. 해결코드를 보면 주워진 deadline을 새롭게 갱신해 준다(renewedDeadline). 이렇게 주워진 마감일을 앞당김으로써 주중에도 정규근무(regularWork)가 가능하게 해준것이다. 즉, 주말에는 regularWork가 불가능하다는 조악한 상황설정을 문제에서 주워진 값에 변형을 가해줌으로써(deadline => renewedDeadline) 없애 버린것이다. 이게 참 높이 평가되는 문제 해결력이다.

 

비슷비슷한 문제일지라도 문제의 조건과 무엇을 구하는지에 따라 설계기법이 달라진다.
마감시간과 작업일수가 있는 스캐줄링 에서 최소시간외 근무일수(27112, 시간외 근무 멈춰). 단 안되면 그냥 -1출력 =>Greedy

마감시간이 있는 스케줄링에서 최대이익(작업일수 없음, 마감시간과 이득만 있음) => Greedy

(퇴사2문제)작업일수가 있는 스케줄링에서 최대이익 (작업일수, 이득만 있음) =Dynamic

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


class Process implements Comparable<Process>{
    private int deadline;
    private int duration;

    public Process(int deadline, int duration){
        this.deadline=deadline;
        this.duration=duration;
    }
    public int getDeadline() {
        return deadline;
    }

    public int getDuration() {
        return duration;
    }
    @Override
    public int compareTo(Process p){
        return getDeadline()-p.getDeadline();
    }
}
public class Main{

    public static void deadlineScheduleWithDuration(PriorityQueue<Process>pq){
        //answer은 답인동시에 시간외 근무 일수
        int regularWork=0;
        int answer=0;
        while(!pq.isEmpty()){
            Process p=pq.poll();
            //어떻게 주말에는 정규근무가 가능하지 않은데 이렇게 코드를 짜서 통과가 될까?
            // deadline을 앞당김으로써 주말에도 정규근무가 가능하도록 한 것이다!!!

            int renewedDeadline=p.getDeadline();
            renewedDeadline-=(renewedDeadline/7)*2;
            if(p.getDeadline()%7==6)
                renewedDeadline--;
            regularWork+=p.getDuration();
            if(regularWork>renewedDeadline){
                answer+=(regularWork-renewedDeadline);
                regularWork=renewedDeadline;
            }
            if(answer>p.getDeadline()){
                answer=-1;
                break;
            }
        }
        System.out.println(answer);

    }

    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<Process>pq=new PriorityQueue<>();
        
//위와 같이 Comparable 인터페이스를 구현하게 하지않고 PriorityQueue에 직접적으로 아래와 같이 정렬기준을 심어줄수 있다.
//        PriorityQueue<Process>pq=new PriorityQueue<>((a,b)->a.getDeadline()-b.getDeadline());
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int deadline=Integer.parseInt(st.nextToken());
            int duration=Integer.parseInt(st.nextToken());
            pq.add(new Process(deadline, duration));
        }
        deadlineScheduleWithDuration(pq);

    }

}