백준 17420 깊콘이 넘쳐흘러

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/17420

(1) 조건 분석 📊

기프티콘마다 사용 기한과 사용 계획일이 있다.

1. 기프티콘은 무조건 사용 계획일 순서대로 써야 한다.
2. 사용 기한은 30일 씩 계속 연장할 수 있다.
3. 기프티콘을 사용할 때 해당 기프티콘은 무조건 사용기한이 제일 짧아야 한다.
4. 사용 계획일이 겹치면서 사용 기한도 겹치는 경우 아무거나 써도 되고, 그때 복수로 여러 개 사용해도 된다.

이때, 기프티콘의 연장을 최소로 하면서 모든 기프티콘을 계획일에 사용하려고 한다. 연장 최소 횟수는 어떻게 되는가?

2. 코드가 나오기까지 🛠️

KEY WORD: 그리디 알고리즘, 정렬, 우선순위 큐

기프티콘의 사용 기한은 다음과 같은 원칙을 지켜야 한다.

1. 최소한 자신의 사용 계획일보단 사용 기한이 길어야 한다.
2. 과거 날짜에 사용한 기프티콘 중 사용 기한이 가장 긴 것보다 사용기한이 길어야 한다.

1번은 당연한 소리이고, 2번에 대해서 짚고 넘어가겠다.

(1) 이전 날짜의 최장 기한 기프티콘보다 사용 기한 길어야 함.

현 날짜에 사용하는 기프티콘을 A라고 해보자. A를 사용하는 시점에 A는 미래 시점에 사용할 어느 기프티콘보다 사용기한이 짧아야 한다. 기프티콘의 사용 기한을 축소할 수 없으므로, 이는 A보다 기한이 짧은 미래에 쓰는 기프티콘을 A보다 길게 연장해야함을 알 수 있다.

이때 중요한 것은 이전 날짜라는 것이다. 동일 날짜에 함께 쓰는 기프티콘들 끼리의 경우, 사용기한이 짧은 순으로 그 날 연속해서 쓰면 되므로, 서로 기한을 늘려줄 필요가 없다.

예를 들어 다음과 같다고 해보자.

"깊티 1": (기한: 24, 사용 계획일: 25),
"깊티 2": (기한: 2, 사용 계획일: 30),
"깊티 3": (기한: 3, 사용 계획일: 30),
"깊티 4": (기한: 29, 사용 계획일:30),
"깊티 5": (기한: 25, 사용 계획일:35)

먼저 깊티1을 써야 한다. 하지만, 자신의 사용 계획일보다 기한이 짧고, 뿐만 아니라 나머지 깊티와 비교하여도 기한이 제일 짧지 않다. 따라서 자신의 기한을 30일 연장함과 더불어 나머지 깊티도 전부 연장해야 한다.

"깊티 1": (기한: "54", 사용 계획일: 25), // 1번 연장
"깊티 2": (기한: "62", 사용 계획일: 30), // 2번 연장
"깊티 3": (기한: "63", 사용 계획일: 30), // 2번 연장
"깊티 4": (기한: "59", 사용 계획일:30),  // 1번 연장
"깊티 5": (기한: "55", 사용 계획일:35)   // 2번 연장

먼저 깊티1을 30일 추가하여 1번 연장한 뒤에 나머지 깊티들은 54일보다 더 길게 기한을 연장한다. 이후 깊티1을 쓰면 나머지 깊티 2 ~ 5 까지 써야 하는데, 깊티 2~4 까지는 사용 계획일이 같음을 알 수 있다.

만약 위에 적힌 순서대로 깊티를 쓴다면 마지막 깊티4는 63보다 기한이 길어야 하기에 한 번 더 연장해야 하고, 이에 따라 깊티 5도 연쇄적으로 연장해야한다. 이미 이것은 최소 연장 횟수보다 길어짐을 알 수 있다.

같은 계획일의 깊티에 대해서는 다시 정렬해야 한다.

"깊티 4": (기한: "59", 사용 계획일:30),  
"깊티 2": (기한: "62", 사용 계획일: 30), 
"깊티 3": (기한: "63", 사용 계획일: 30), 
"깊티 5": (기한: "55", 사용 계획일:35)  

이러면 30일에는 쿠폰 연장 없이 당일 쿠폰을 모두 쓸 수 있다.
깊티 5는 자신보다 이전 날짜 모든 깊티보다 기한이 길어야 한다. 즉 제일 기한이 길었던 63보다 길어야 하므로 한 번 더 연장한다.

"깊티 5": (기한: "85", 사용 계획일:35) // 1번 더 연장

(2) 구현 방법

근데 기프티콘이 총 $100,000$ 개여서 이중 반복문을 할 수 없다. 그렇기에 위와 같이 같은 사용 계획일 깊티를 모아 재정렬 같은 작업을 할 수 없다. 따라서 구현 시 생각해야할 점은 한 번의 순회로 모두 계산이다.

A. 세팅

우선순위 큐를 만들고 다음과 같이 정렬한다.

1. 사용 계획일이 이른 순으로 정렬
2. 사용 계획일이 같다면 사용 기한이 짧은 순으로 정렬

   B. 이전 날짜 깊티 최대 기한 vs 현 깊티 사용 계획일 중 max

   현재 깊티의 사용 기한을 늘릴 때는 이전 날짜 깊티의 최대 기한과 현 깊티의 사용 계획일 중 최대값보다 크게 늘려줘야 한다. 이미 이 둘보다 크다면 따로 계산할 필요 없다.

   C. 기한이 동일한 구간 확인

   다음 두 변수를 세팅해서 운용한다.
3. prev_max: 이전 구간 깊티들 중 최장 사용 기한
4. section_max: 현재 구간 깊티들 중 최장 사용 기한

우선순위 큐에 깊티를 무한대 사용기한으로 하나 넣어둔다. -> NULL POINTER ERROR 방지용

3. 현재 확인 중인 깊티와 다음에 확인할 깊티의 사용 계획일이 겹치는지 확인한다.
   1. 만약 같다면, 동일 구간이므로 section_max만 업데이트
   2. 만약 다르다면, prev_max를 section_max로 갱신한다.

여기서 prev_max가 B에서 확인하는 이전 날짜 깊티 최대 기한이다.

(3) 시간복잡도 분석 ⏳

한 번의 순회에서 계산하므로 최종 $O(100,000)$ 이다.

3. 코드 🌐

(1) SUDO CODE 💬

+ 1. 우선순위 큐 (사용 계획일 오름차순, 사용 기한 오름 차순) 만들어서 모든 값 집어넣기
-    (1) 무한대 사용 기한을 가지는 더미 기프티콘도 우선순위 큐에 넣기 (null pointer 방지)
+ 2. 우선순위 큐에서 N개 빼며 다음을 반복
-    (1) 이전 날짜 깊티 중 최장 사용 기한과 현 깊티의 사용 계획일 중 최대값 구하기
-    (2) ((1)에서 구한 Max값 - 현 날짜 깊티 사용 기한) 만큼 현 깊티 사용 기한 연장
-        연장한 횟수를 답에 누적
-    (3) 다음 깊티도 현 깊티와 같은 사용 계획일인지 확인 (구간 확인)
        a. 다르면 현 구간의 최장 기한으로 이전 구간 최장 기한 갱신

(2) JAVA CODE ☕

import java.util.*;  
import java.io.*;  
 // b 3109 빵집  
public class Main {  
    static class Gifticon{  
        int due;  
        int use_plan;  

        public Gifticon(int due, int use_plan){  
            this.due = due; // 사용기한  
            this.use_plan = use_plan; // 사용할 계획  
        }  

        @Override  
        public String toString(){  
            return String.format("(due: %d, use_plan: %d)", this.due, this.use_plan);  
        }    }    static int N;  
    static PriorityQueue<Gifticon> pq = new PriorityQueue<>((o1,o2) -> {  
        if(o1.use_plan == o2.use_plan) return o1.due - o2.due;  
        return o1.use_plan - o2.use_plan;  
    });    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
        StringTokenizer dues = new StringTokenizer(br.readLine());  
        StringTokenizer dates = new StringTokenizer(br.readLine());  
        for(int i = 0; i < N; i++){  
            pq.add(new Gifticon(Integer.parseInt(dues.nextToken()), Integer.parseInt(dates.nextToken())));  
        }        pq.add(new Gifticon(Integer.MAX_VALUE, Integer.MAX_VALUE));  

        int prev_max = 0;  
        int section_max = 0;  
        long answer = 0;  

        for(int i = 0; i < N; i++){  
            Gifticon now = pq.poll();  
            // 현재 값에 대한 계산  
            int minimum_due = Math.max(prev_max, now.use_plan); // 이전 구간 중 최대 기한 vs 자신의 계획일 중 더 높은 것  
            int extension_cnt = quotient(minimum_due - now.due ) + (remainder(minimum_due - now.due) != 0? 1 : 0);  
            answer += extension_cnt;  
            section_max = Math.max(section_max, now.due + extension_cnt*30);  
//            System.out.printf("%s, 연장 횟수: %d, 이전 구간 최대값: %d, 현 구간 최대값: %d\n", now, extension_cnt, prev_max, section_max);  
            // 구간이 달라질 때,  
            if(now.use_plan != pq.peek().use_plan) {  
                prev_max = section_max;  
            }        }        System.out.println(answer);  


    }  
    public static int quotient (int target){  
        if(target <= 0) return 0;  
        return target/30;  
    }  
    public static int remainder (int target) {  
        if(target <= 0) return 0;  
        return target%30;  
    } 
}

4. 트러블 슈팅 or 배운 점📝

문제 설명이 너무 별로다. 이해를 초반에 못했다. 왜냐면 문제에서는 깊티 중 사용 기한이 제일 짧은 것만 사용하면 된다고 했지, 깊티의 사용기한에 그것을 무조건 써야 한다는 이야기가 없었기 떄문이다.