깊콘이 넘쳐흘러 (17420번) - 백준 (BOJ)

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

17420번: 깊콘이 넘쳐흘러

 

 

백준 - 깊콘이 넘쳐흘러 (17420번)

 

난이도 : Gold 1

알고리즘&자료구조 : Greedy (그리디) & Sorting (정렬)

시간복잡도 (Time Complexity) : O(NlogN)

---

★ 핵심 Idea ★

특정 시점 X에서 기프티콘을 사용할 때,

X보다 뒤에 사용할 기프티콘들의 남은 사용기한이

X에 사용할 기프티콘들의 남은 사용기한보다 더 커야한다.

 

 

< 전체 코드 >

 

class Gifts():
    def __init__(self, N):
        extension = 0
        info = [[a, b] for a, b in zip(map(int, input().split()), map(int, input().split()))]
        for i in range(N):
            a, b = info[i]
            if a >= b:
                continue
            x = ((b-a-1)//30) + 1
            extension += x
            info[i][0] = a + 30*x

        info.sort(key=lambda x: x[1])

        thres = 0
        cur, due = info[0]
        for a, b in info:
            if b != due:
                thres = cur
                cur, due = a, b
            if a < thres:
                x = ((thres-a-1)//30) + 1
                a += 30*x
                extension += x
            cur = max(cur, a)

        self.extension = extension


if __name__ == '__main__':
    gifts = Gifts(int(input()))
    print(gifts.extension)

---

 

① 기프티콘 정보들을 입력받은 뒤,

남은 기한이 사용 날짜보다 크도록 기한을 연장해주고,

사용 날짜에 맞춰서 오름차순 정렬한다.

 

extension = 0
info = [[a, b] for a, b in zip(map(int, input().split()), map(int, input().split()))]
for i in range(N):
    a, b = info[i]
    if a >= b:
        continue
    x = ((b-a-1)//30) + 1
    extension += x
    info[i][0] = a + 30*x

info.sort(key=lambda x: x[1])

 

 

 

② for 문으로 배열을 순회하면서,

"due", "thres", "cur" 이렇게 3가지 변수를 통해 기프티콘들을 갱신해준다.

 

현재 사용 날짜 "due"에 해당하는 기프티콘들의 남은 기한들이,

이전 사용 날짜에 해당하는 기프티콘들의 남은 기한 "thres" 보다 크도록 갱신한다.

갱신하는 횟수를 "extension"에 계속 누적시켜준다.

 

또한 현재 사용 날짜 b에 해당하는 기프티콘들의 남은 기한들 중 가장 큰 값을 "cur"에 저장해두고,

다음 번 "thres" 로 사용해주면 된다.

 

thres = 0
cur, due = info[0]
for a, b in info:
    if b != due:
        thres = cur
        cur, due = a, b
    if a < thres:
        x = ((thres-a-1)//30) + 1
        a += 30*x
        extension += x
    cur = max(cur, a)

 

 

 

③ 지금까지 갱신 횟수인 "extension"을 출력해주면 정답이 된다.

 

self.extension = extension

gifts = Gifts(int(input()))
print(gifts.extension)