[Baekjoon] 13904번 : 과제

1. 문제

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

• 그리디 문제

// 문제
웅찬이는 과제가 많다. 
하루에 한 과제를 끝낼 수 있는데, 
과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 
과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 
마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 
웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

// 입력
첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 
d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. 
d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

// 출력
얻을 수 있는 점수의 최댓값을 출력한다.

// 예제 입력 1 
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

// 예제 출력 1 
185

// 힌트
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 
세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

2. 핵심 아이디어

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = []
result = [0 for _ in range(1000)]

for i in range(n) :
  a, b = map(int, input().split())
  arr.append([a, b])

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

for i in range(n) :
  for j in range(arr[i][0]-1, -1, -1) :
    if result[j] == 0 :
      result[j] = arr[i][1]
      break

print(sum(result))

4. Java 문제풀이