📚 17420 - 깊콘이 넘쳐흘러

깊콘이 넘쳐 흘러

 

이해

당분간, 그리디 알고리즘 50개 풀 예정! (그리디 알고리즘 실력 상승시키기 위해 도전!)

시작하기에 앞서, 이번 문제 쉬운 것 같으면서도, 답을 구하기 위한 계산식이 상당히 복잡함에 검색 했다.
설명 잘되어 있는 곳

24	2	3	29	2
25	35	30	30	30

일 때 어떻게 해야할까?

문제를 읽어보면 알 수 있다!

문제 입력 설명 따르면 i번째 기프티콘은 Bi 일 후에 써야 하는데 사용 기한이 제일 촉박한 기프티콘을 먼저 사용해야 한다면 Bi일 후에 써야할 i번째 기프티콘의 사용 기한이 가장 적게 남아야 한다는 의미로 해석할 수 있다.

이는, Bi를 먼저 체크하고, B 값이 같다면, A 값을 기준으로 정렬을 해야 한다.

정렬을 한 후, Bi 값보다 큰 수 이상으로는 (Ai부터 An까지) 기프티콘 일 수를 연장해야 한다. (30일씩)

 

24	2	3	29	2
25	35	30	30	30

 

24	2	3	29	2
25	30	30	30	35

 

54(24+30)	62(2+60)	63(3+60)	59(29+30)	92(2+90)
25	30	30	30	35

• Bi가 30구간은 54를 기준으로 판결한다.
• Bi가 35구간은 63을 기준으로 판결한다. (30구간 중 가장 큰 값 63)

 

✔️ 문제 로직

(1) Bi 오름차순 정렬, 값이 같다면 Ai 오름차순 정렬
(2) for문으로 arr = ((A, B))를 순회한다.

• 이전 구간의 최댓 값이 Ai보다 클 경우
  이전 구간 값 : 이전 갱신된 Ai(1~(i-1))최댓값 or 이전 Bi(1~(i-1)) 최댓값
  • 이전 구간의 최댓값보다 기프티콘 현재 사용 예정일이 더 크다면 갱신한다.
  • 연장 횟수 계산할 때 (math.ceil 올림 메서드 사용한다.)
  • answer 값을 연장 횟수 만큼 증가시킨다.
  • 그리고, Ai의 최댓값을 찾는다.
• 구간 변경 시, 이전 구간의 최댓값을 현재 구간 중 최댓값으로 갱신한다.

 

소스

import sys
import math

read = sys.stdin.readline

n = int(read())
A = list(map(int, read().split()))
B = list(map(int, read().split()))

arr = []

for r1, r2 in zip(A, B):
    arr.append([r1, r2])

# B를 기준으로 정렬
# A를 기준으로 정렬
arr.sort(key=lambda x: (x[1], x[0]))

# 0번째 index의 B값을 p에 저장한다. (첫 번째 B값으로 A의 위치를 확인한다.)
previous = arr[0][1]
cur_max = -1
answer = 0
cnt = 0

for i in range(n):
    # 현재 Ai 값이
    # - 이전 1 ~ i - 1 구간 계산된 결과 중 최댓 값 Ai 보다 작거나
    # - 이전 1 ~ i - 1 구간의 Bi의 최댓 값보다 작을 때
    # Ai값을 갱신해줘야 한다. (30일 x t)
    # 현재 t값을 구해서 갱신하는 것이다.
    if previous > arr[i][0]:
        previous = max(previous, arr[i][1])
        # if previous < arr[i][1]:
        #     previous = arr[i][1]

        cnt = math.ceil((previous - arr[i][0]) / 30)
        arr[i][0] += cnt * 30  # 30일씩 추가해줘야한다.
        answer += cnt

    # - 이전 1 ~ i - 1 구간 계산된 결과 중 최댓 값 Ai 보다 작거나
    # - 이전 1 ~ i - 1 구간의 Bi의 최댓 값보다 작을 때
    # 이 두 구간중 가장 큰 값으로 갱신해야 한다.
    # arr[i][0]은 갱신된 상태
    cur_max = max(cur_max, arr[i][0])

    # 만약, 현재 Bi와 다음 Bi+1 값이 다르다면, 이전 값을 갱신해준다.
    # Bi와 다음 Bi+1 가 같다면, 그대로 유지한다.
    if i + 1 < n and (arr[i][1] != arr[i + 1][1]):
        previous = cur_max


print(answer)

 

---

참고

• 설명 잘되어 있는 곳