Apprentice Learning Trajectory 풀이(boj 19218, NERC 2019 A번)

문제 설명

---

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

19218번: Apprentice Learning Trajectory

n명의 master가 있고 각 master는 [a, b] 기간동안 sword를 만들 수 있고 하나의 sword를 만드는데 t초가 걸린다.

 

forge는 하나라서 여러명의 master가 동시에 이용할 수 없다. 이 때 생산할 수 있는 sword의 최대 갯수를 구하면 된다.

 

예제 입력)

 

 

 

 

그리디 알고리즘

---

잘 알려진 그리디 알고리즘에 의하면 가장 빨리 끝나는 스케줄만 선택하면 최적이다.

 

이 때 n개의 스케줄 중에서 가장 빨리 끝나는 것을 계속 선택하면 a와 b는 최대 10^18이고 t는 1일 수 있기 때문에 시간초과가 난다.

스케줄의 선택이 최대 10^18번 반복 될 수 있기 때문이다.

 

 

 

 

최적화

---

따라서 다음과 같이 최적화를 한다.

 

 

n개의 시작시간과 n개의 종료시간으로 나눠진 2n개의 interval을 생각해보자. 각 interval에서는 가장 작은 t는 정해져있다.

따라서 interval의 길이가 L이라고 한다면 만들 수 있는 sword의 수는 L/min(t_i)이다.

우선순위큐로 최소 t를 관리하면서 라인 스위핑을 하면 O(nlogn)의 시간복잡도로 수행 가능하다. 여기까지는 생각하기 쉽다. 

 

하지만 문제는 경계값이다. 구간이 시작되거나 끝날 때는 어떤 스케줄을 선택해야할까? 아래 예시를 보자.

 

위의 최적화에 의해서 구간은 [0, 4], [4, 6], [6, 10]이다. 눈으로 확인 할 수 있는 최적해는 2이다. (1에서 2개 선택)

 

만약 경계값에서 선택을 안하고 위 최적화대로 진행한다면.

 

[0, 4] : 선택할 수 있는 스케줄이 없다.

[4, 6] : t가 가장 작은 스케줄을 선택한다. (2에서 1개 선택)

[6, 10] : 선택할 수 있는 스케줄이 없다.

 

그리고 1개는 최적해가 아니다.

 

위 예시에서 보다싶이 interval이 시작될 때 스케줄을 선택하는 것도 고려해야하고 이 때 그리디 알고리즘이 성립하려면 가장 빨리 끝나는 스케줄을 선택해야한다.

 

 

 

 

경계값에서의 선택

---

시작시간 : a / 종료시간 : b

 

[a 와 b를 2n개 넣고 스위핑을 했을 때의 문제점]

각 a마다 선택가능한 스케줄이 있어도 다음 a에서 더 일찍 끝나는 스케줄이 있을 수 있다.

 

따라서

[a 대신에 a+t를 넣고 정렬하자]

이렇게 정렬해서 각 a+t마다 a에서 선택이 가능했었다면 답에 +1을 해준다.

경계값에서 끝나는 시간인 a+t로 정렬했기 때문에 가장 먼저 확인하는 a+t가 경계값에서 가장 빨리 끝나는 스케줄이다.

즉, 그리디 알고리즘을 만족한다.

 

 

 

 

소스코드

---

from heapq import *
import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    sweep = []

    for i in range(N):
        a, b, t = map(int, input().split())
        sweep.append((a + t, -1, t))
        sweep.append((b, 1, t))

    ans = 0
    prv = 0
    pq = []
    del_pq = []
    for cur, flag, t in sorted(sweep):
        # 최적화 부분 : L // min(t_i)
        if pq:
            min_t = pq[0]
            L = cur - prv
            n = L // min_t
            ans += n
            prv += n * min_t
        # 삭제
        if flag == 1:
            heappush(del_pq, t)
            while del_pq and pq[0] == del_pq[0]:
                heappop(pq)
                heappop(del_pq)
        # 추가
        else:
            # a에서 선택이 가능했었다면 ans += 1
            if prv <= cur - t:
                ans += 1
                prv = cur
            heappush(pq, t)

    print(ans)