240313[BOJ/백준] 7983. 내일 할거야

 

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

7983번: 내일 할거야

---

나의 코드

1. 과제하는 날을 체크하며 계산(메모리 초과)

import sys

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

arr.sort(key=lambda x: x[1], reverse=True) #2차원 배열에서 [di,ti]라면 ti에 대해 역정렬
# print(arr)
deadline = arr[0][1] # 제일 늦은 과제 마감일
check = [0]*(deadline+1)

for i in range(len(arr)):   # 과제 마감일이 제일 늦은 것부터 탐색
    for j in range(arr[i][0]):
        day = arr[i][1]-j    # 과제 하는 날
        while check[day] == 1:  # 이미 과제를 하는 날이라면
            day -= 1            # 과제 마감일을 하루씩 당긴다.
        check[day] = 1          # 과제하는 날이 아니라면 과제를 한다.

count = 0
for k in check:   # 앞부터 연속으로 0인 갯수 세기
    if k == 0:
        count += 1
    else:
        break

print(count-1)  # check가 0일부터 시작이어서 1 빼줌

 

2. 과제마감일에 따라 계산하며 과제 시작일 계산(성공)

import sys

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

arr.sort(key=lambda x: x[1], reverse=True) #2차원 배열에서 [di,ti]라면 ti에 대해 역정렬

ans = arr[0][1] - arr[0][0]
for i in range(1, n):
    start = arr[i][1] - arr[i][0]
    if arr[i][1] <= ans:
        ans = start
    else:
        ans -= arr[i][0]

print(ans)

 

결과

---

강의 때 회의실을 가장 효율적으로 쓰는 방법에 대해 지나가듯이 들었던 기억이 있다. 그래서 그 방법을 뒤집어서 문제를 풀면 되겠다고 생각해서 알고리즘을 짰다. 결과가 나왔는데 메모리초과라니... 메모리초과는 한번도 겪어보지 못해서 바로 친구들 코드를 봤닼ㅋㅋㅋㅋㅋㅋㅋ 나는 과제를 이미 한 상황이라면 과제 마감일을 1씩 빼면서 과제시작일을 계산했다. 다른 친구들은 과제마감일이 다음 과제 시작일보다 빠를지 느릴지에 따라 바로 계산하는 방법으로 메모리초과 문제를 해결했다. 나는 과제하는 날을 체크하는 리스트 하나를 더 만들어서인지 메모리초과가 발생한 것 같다. 그와중에 제일 나중 과제시작일(ans) 구했는데 1부터 범위 지정안해줘서 틀렸닼ㅋㅋㅋㅋㅋㅋㅋ