깊콘이 넘쳐흘러
정우는 생일을 맞아 친구들에게 기프티콘을 N개 선물받았다. 어떤 기프티콘을 언제 쓸지 다 계획을 정해놨는데, 멍청한 정우는 기프티콘에 기한이 있다는 사실을 까맣게 잊고 있었다. 다행히 기프티콘에는 기한 연장 기능이 있다. 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다.
정우는 기프티콘의 기한 연장을 너무 귀찮아하기 때문에, 기한 연장을 최소한으로 하고 싶어한다. 그리고 정우는 강박증이 있어서, 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다. 단, 기한이 가장 적게 남은 기프티콘이 여러 개라면 그 중 아무거나 선택할 수 있다. 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다.
최소 횟수로 기한 연장을 하면서 기프티콘을 다 쓸 수 있도록 정우를 도와주자.
입력
첫째 줄에 기프티콘의 수 N이 주어진다.
둘째 줄에 A1, A2, ..., AN가 주어진다. 이는 i번째 기프티콘의 남은 기한이 Ai일이라는 뜻이다.
셋째 줄에 B1, B2, ..., BN가 주어진다. 이는 i번째 기프티콘을 Bi일 뒤에 사용할 계획이라는 뜻이다.
출력
첫째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력한다.
정답이 32비트 정수를 넘을 수 있으므로 유의하라.
풀이
처음문제를 읽고 "머야.. 되게 쉽네..?"라고 생각했다가 코가 깨지지 못해 터졌습니다. 강박증 때문에 기간이 가장 짧은 깊콘만 쓸 수 있다니...이래서 문제를 꼼꼼하게 읽어봐야 되는 거군요.. 예를 들어, 깊콘의 남은 기간을 연장했을 경우 깊콘의 남은 기간이 짧은 것만 사용할 수 있기 때문에 아직 계획이 아닌 깊콘도 연장(!중요) 해줘야 합니다.
import sys
import math
input = sys.stdin.readline
n = int(input())
rest = list(map(int, input().split())) # 남은 기간
plan = list(map(int, input().split())) # 계획일
arr = []
for r, p in zip(rest, plan): # 기간과 계획을 묶음
arr.append([r, p])
arr = sorted(arr, key=lambda x : (x[1], x[0]))
# 계획일을 기준으로 정렬, 계획이 같으면 남은기간 순으로 정렬
p = arr[0][0] # 구간 최댓값 정의
th = arr[0][1] # 구간 기준점 정의
cnt = 0
for i in range(n):
if th > arr[i][0]: # 남은 기간이 기준점보다 짧다면 연장
tmp = math.ceil((th - arr[i][0]) / 30)
cnt += tmp
arr[i][0] += tmp * 30
p = max(p, arr[i][0])
# 다음 계획일의 구간의 값이 달라진다면 구간 기준점 재정의
if i+1 < n and arr[i][1] != arr[i+1][1]:
th = max(p, arr[i+1][1])
print(cnt)이 풀이에서 핵심은 구간 최댓값과 구간 기준점입니다. 우선, 남은 기간과 계획일로 각각 받은 배열을 반복문을 이용해서 하나의 배열로 묶어줍니다. 이렇게 이중배열 arr이 생성되었습니다. 이제 구간 최댓값과 구간 기준점을 각각 배열의 첫번째 항의 0번, 1번 인덱스로 초기화해줍니다. 구간 기준점은 가장 빨리 사용할 깊콘의 남은 기간입니다. 이 과정을 이용해서 강박증이 있는 정우를 위해 한번 더 연장해줄 수 있습니다. 이후 구간 최댓값은 원래 값과 현재의 남은 기간을 비교해서 큰 값으로 갱신해줍니다. 이 과정으로 다음 계획일이 같은 구간에서 새로운 기준점을 마련할 수 있습니다.
