728x90
https://www.acmicpc.net/problem/13904
점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다.
우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다.
해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다.
결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다!
(여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
arr=[]
cnt = -1
ans = 0
for i in range(n):
d,w = map(int,input().split())
arr.append([d,w])
cnt = max(cnt,d)
arr = sorted(arr,key=lambda x:-x[1])
visited = [0 for _ in range(cnt+1)]
for day,weight in arr:
if visited[day]==0:
visited[day] = weight
else:
day-=1
while day:
if visited[day]==0:
visited[day] = weight
break
day -= 1
for w in visited:
ans += w
print(ans)
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 27211번 도넛 행성 (0) | 2023.01.20 |
---|---|
[백준/파이썬] 12100번 2048 (0) | 2023.01.16 |
[백준/파이썬] 2225번 합분해 (0) | 2023.01.09 |
[백준/C++] 1647번 도시 분할 계획 (0) | 2023.01.05 |
[백준/C++] 2473번 세 용액 (1) | 2023.01.05 |