[백준] 13904번: 과제(다시)

-문제: https://www.acmicpc.net/problem/13904

문제가 이해가 잘 가지 않았던 문제. 특정규칙을 찾을 수 없어서 헤맸다

근데 정답률이 50퍼라니,, 의아했던 문제다 

근데 막상 풀이를 보니 쉬워서 그리 어려운 문제는 아닌 것 같기도 하고 

 

 

-정답풀이:

0열을 기준으로 나열하거나 1열을 기준으로하면 정답이 안 나와서 뭐를 기준으로 했는지 찾아봤는데

해당 과제의 마감일을 기준으로 생각하면 정답이 나온다

마감 6일째 할 수 있는 과제는  [6,5] 과제만 남고 5점을 추가하면된다

5일째에는 없고,

4일째에 할 수 있는 과제는 [4,10],[4,40],[4,60] 인데 여기서 점수 최댓값은 [4,60]이므로 60점을 추가한다.

3일째에 할 수 있는 과제는 [4,40],[4,10],[3,30]인데 여기서 점수 최댓값은 [4,40]이라서 40점을 추가한다

2일째에 할 수 있는 과제는 [2,50],[3,30],[4,10]이 남는데 여기서 점수 최댓값은 [2,50]이라서 50점을 추가한다

1일 째에 할 수 있는 과제는 [3,30],[4,10],[1,20]인데 여기서 최대 점수는 [3,30]이므로 30을 추가하면 정답이다 

더 이해하려면 다음 블로그를 참고하면 된다.  https://chinpa.tistory.com/34

 

8번 라인을 보면 주어진 행렬에서 0열 기준으로 큰수부터 나열하고, 1열을 기준으로 다시 나열을 했는데 이렇게 하면 위의 원리를 적용한 행렬을 구할 수 있다.

i행렬의 남은 마감일부터(인덱스니까 1빼고) 0번 인덱스까지 거꾸로 실행한다

그 날의 스케줄이 비어있으면 그날에 해당 과제의 점수 저장

과제를 여러번 저장하지 않도록 break 실행 

 

n=int(input())
work=[]
ans=[0]*1000

for i in range(n):
    work.append(list(map(int,input().split())))
    
work.sort(reverse=True, key=lambda x:x[1])

for i in range(n):
    for j in range(work[i][0]-1,-1,-1):
        if ans[j]==0:
            ans[j]=work[i][1]
            break
print(sum(ans))