백준 6068번: 시간 관리하기 (Python/Java)

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

6068번: 시간 관리하기

 

 

 

접근

---

만일 문제 조건이 '존이 일을 가장 빨리 마칠 수 있는 시간'이라면 그냥 0부터 차례대로 일을 나열하면 될 것이다. 하지만 문제 조건은 '존이 가장 늦게 일어나도 되는 시간'이다. 즉, 최대한 일을 늦게 마쳐야 한다는 뜻이다. 때문에 0부터 차례대로 일을 나열하면서 최대한 일을 늦게 마치는 경우를 찾는다면 그 경우의 수가 수없이 많아지기 때문에 제대로 된 답을 찾을 수 없다.

 

그렇다면 반대로 생각해보자. 답을 찾기 시작하는 지점을 0부터 시작하는 것이 아니라 마쳐야 하는 시간의 최댓값부터 답을 찾기 시작하는 것이다. 문제의 예제의 경우, 마쳐야 하는 시간들 중 최댓값은 20이다. 그럼 20에서부터 일을 하나씩 수행해가는 것이다. 

 

위 예제를 살펴보자. [[3,5], [8, 14], [5, 20], [1, 16]]이 주어졌다. 이 배열을 '일을 마쳐야 하는 시간' 기준으로 역순 정렬하면 [[5, 20], [1, 16], [8, 14], [3, 5]]이 나온다. 이제 일을 마쳐야 하는 시간 중 가장 늦은 시간이 20이라는 것을 알 수 있다. 이제 20부터 역으로 생각해보자. 정렬된 배열 중 첫 번째 일을 언제 시작해야 가장 늦게 끝낼 수 있을까? 16이다. 16~20까지 일을 하면 되기 때문이다. 그다음을 살펴보자. 1의 시간을 들여서 16까지 끝내야 한다. 하지만 이미 이전 단계에서 16~20까지의 시간을 썼다. 그렇다면 15 시간 때 1의 시간을 들여야 한다. 이와 같은 방법으로 역순으로 시간을 계산하면 최종적으로 남는 시간이 있는데, 그게 바로 이 문제에서 찾는 답이다.

 

그림으로 표현하면 이렇다. 첫 번째 일(TASK 1)은 20부터 5의 시간이 드니 15의 시간이 남는다. 두 번째 일은 1의 시간이 들어서 14의 시간이 남고, 세 번째 일은 8의 시간이 들기 때문에 6의 시간이 남는다. 6까지 여유가 되지만 마지막 일은 5에서 끝나야 한다. 때문에 5에서 마지막 일이 걸리는 시간 3을 빼면 2가 남고 이게 답이 된다.

 

 

 

풀이

---

Python

workNum = int(input())

board = [[0, 0] for i in range(workNum)]
for i in range(workNum):
    termNum, endNum = map(int, input().split())
    board[i][0], board[i][1] = termNum, endNum

board = sorted(board, key = lambda x: (x[1], x[0]), reverse = True)

resultCheck = True
thisTime = board[0][1]
for i in range(workNum):
    
    if board[i][1] <= thisTime:
        thisTime = (board[i][1] - board[i][0])
    else:
        thisTime -= board[i][0]

if thisTime >= 0:
    print(thisTime)
else:
    print(-1)

 

Java

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        
        int workNum = Integer.parseInt(scan.nextLine());

        int[][] board = new int[workNum][2];
        for(int i = 0 ; i < workNum ; i++){
            String[] firstLine = (scan.nextLine()).split(" ");
            board[i][0] = Integer.parseInt(firstLine[0]);
            board[i][1] = Integer.parseInt(firstLine[1]);
        }

        Arrays.sort(board, new Comparator<int[]>(){
            @Override
            public int compare(int[] firstNum, int[] secondNum){
                return secondNum[1] - firstNum[1];
            }
        });
        Arrays.sort(board, new Comparator<int[]>(){
            @Override
            public int compare(int[] firstNum, int[] secondNum){
                if(secondNum[1] - firstNum[1] == 0){
                    return secondNum[0] - firstNum[0];
                }
                return secondNum[1] - firstNum[1];
            }
        });

        long thisTime = board[0][1];
        for(int i = 0 ; i < workNum ; i++){
            if(thisTime >= board[i][1]){
               thisTime = (board[i][1] - board[i][0]);
            }else{
                thisTime -= board[i][0];
            }
        }

        if(thisTime >= 0){
            System.out.println(thisTime);
        }else{
            System.out.println(-1);
        }

    }

}

 

 

 

후기

---

포스팅하며 풀이과정을 살펴보다가 생각난 건데, 사실 위 코드에는 굉장히 쓸데없는 정렬이 들어가 있다. 사실 정렬은 '끝내야 하는 시간의 내림차순'으로만 정렬하면 된다. 근데 위 코드에선 끝내야 하는 시간이 같다면 걸리는 시간을 기준으로 다시 내림차순을 해줬다. 전혀 필요 없는 연산이다. 정렬하면 뭐할 거냐, 1+2나 2+1이나 같은 건데 굳이 정렬을...?  왜 그랬냐 물어본다면, 어... 글쎄... 왜 그랬지...? 정신 똑바로 차리고 문제 풀자!!!

 

덧붙여 백준 7983번 '내일할거야(https://www.acmicpc.net/problem/7983)'와 문제 내용만 다르게 적었을 뿐, 완전히 똑같은 문제다. 해당 문제 예제를 7983번 풀이 코드에 넣어도 답을 출력하고 7893번 예제를 ​이 문제 풀이 코드에 넣어도 답을 출력한다.