0313. [BOJ#7983] 내일 할거야

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

7983번: 내일 할거야

2 초

256 MB

2188

1034

823

49.578%

문제

아 과제 하기 싫다. 아무 것도 안 하고 싶다. 더 적극적이고 격렬하게 아무 것도 안 하고 싶다.

있잖아. 내가 아까 책상에다가 n개의 과제 목록을 적어놨어. 각각의 과제 i는 di 일이 걸리고, 오늘로부터 ti 일 안에 끝내야 해. 그러니까 오늘이 0일이면, ti일이 끝나기 전에 제출이야. 과제는 한번 시작하면 쉬지 않고 계속해야 해. 안 그러면 머리 아파 지거든.

근데 있잖아. 내가 지금 너무, 너무 아무 것도 안 하고 싶어. 그래서 오늘은 아무 것도 안 할 거야. 더 중요한 게 뭔지 알아? 사실 나 내일도, 모레도, 아무 것도 안 하고 싶어. 한 며칠 동안은 계속 아무 것도 안하려고. 아. 과제가 있을 때 내가 내일부터 연속으로 최대 며칠동안 놀 수 있는지 궁금하다. 궁금하긴 한데, 난 아무 것도 안 하고 싶어.

좋은 생각이 났다. 너희가 이걸 대신 구해주면, 내가 너희의 맞은 문제 수를 하나 올려줄게.

입력

첫째 줄에는 과제의 개수인 정수 n (1 ≤ n ≤ 106)이 주어진다.

이후 n개의 줄에 각각의 과제를 나타내는 두 정수 di, ti (1 ≤ di, ti ≤ 109)가 순서대로 주어진다. 오늘은 0일이다.

모든 입력에 대해, 오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.

출력

내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다.

---

제출 코드

import sys
input = sys.stdin.readline

N = int(input())

work = []
for _ in range(N):
    a, b = map(int, input().split())
    work.append((a, b)) # [][0]: 걸리는 날짜 / [][1]: 해당 과제 마지막 날

work.sort(key = lambda x: x[1], reverse=True)

days_left = work[0][1] - work[0][0] # 제일 마지막에 할 과제하고 남은 날

for i in range(1, len(work)):
    if days_left >= work[i][1]:
        days_left = work[i][1] - work[i][0]
    else: # days_left < work[i][1]
        days_left = days_left - work[i][0]
print(days_left)

과제 기한이 가장 늦은 날부터 과제에 필요한 날을 빼면서,

만약 남은 날이 다음으로 과제를 늦게 내도 되는 날보다 많다면, 처음 days_left를 구했던 방법으로 days_left를 갱신

그게 아니라 남은 날이 다음으로 과제를 늦게 내도 되는 날보다 적다면,

갱신하지 않고 days_left에서 과제에 필요한 날을 빼는 식으로 구했다.

 

골드 정렬 문제는 인덱스를 물어보면서 시간복잡도와 메모리를 신경쓰게 되는 문제가 많은 것 같다.

 

제출 코드 (첫 시도)

import sys
# sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def working(worked):

    while worked:
        a, b = worked.pop()
        cnt = 0
        for i in range(b, -1, -1):
            if date[i] == 1:
                date[i] = 0 # 0으로
                cnt += 1
                if cnt == a: # 과제다하면
                    break 

N = int(input())

works = []
for _ in range(N):
    a, b = map(int, input().split())
    works.append((a, b)) # [][0]: 걸리는 날짜 / [][1]: 해당 과제 마지막 날
    
works.sort(key = lambda x: x[1])
date = [0] + [1] * works[-1][1]

working(works)
ans = 0
result = 0
for k in date:
    if k == 1:
        ans += 1
    else:
        if result <= ans:
            result = ans
        ans = 0
        
print(result)

멋도 모르고 while-for문으로 풀었던 첫번째 코드.

당연하게 시간초과, 메모리 초과 폭탄을 맞았다ㅠ