💻 Problem
꽉꽉나라의 농부 오리는 아무것도 심어져 있지 않은 텃밭을 하나 가지고 있다. 오리는 그 텃밭에 N종류의 당근을 하나씩 심고 T일 동안 재배할 예정이다.
당근 i(1 ≤ i ≤ N)는 처음에는 wi의 맛을 가지고 있고, 각 당근 i에 사용할 pi만큼 맛을 증가시켜 주는 영양제가 당근 종류별로 T개씩 준비되어 있다. 오리는 당근이 본래의 맛보다 훨씬 맛있어지기를 바라기 때문에 pi는 항상 wi이상의 값을 가지도록 준비했다. 잠이 많은 오리는 매일 오전에만 텃밭에 나와 당근들을 관리한다. 오리는 각 당근 i에 대해 당근 i가 자리에 없다면 당근 i를 심고, 그렇지 않다면 당근 i에 영양제를 하나 준다.
꽉꽉나라에 놀러 온 토끼는 오리가 오전에만 당근을 관리한다는 사실을 알고 오리의 텃밭을 찾아가 당근을 훔쳐 먹을 계획을 세웠다. 토끼는 위장이 작아서 하루에 최대 하나의 당근을 먹을 수 있고 당근을 먹지 않을 수도 있다. 또한 당근 하나를 먹기로 마음먹으면 남기지 않고 먹으며, 오리와 마주치지 않기 위해 오후에만 텃밭에 찾아간다. 토끼는 자신이 먹은 당근의 맛의 합을 최대로 하고 싶어 한다.
T일 동안 토끼가 먹을 수 있는 당근의 맛의 합의 최댓값을 구해보자.
💡 Approach
당근을 중간에 훔쳐 먹고 다시 심는 것보다 최대한 아꼈다가 먹는 게 더 좋다.
이를 역으로 생각하면 T일에서부터 N일 동안 가장 맛있는 당근을 선택하면 된다.
예제 2의 경우를 살펴보자.
| 3 5 1 3 2 9 3 7 |
N = 3, T = 5이다.
중간에 당근을 먹지 않고 최대한 오래 길렀다고 생각해 보자.
5일째에는 아래 세 당근 중 w = 2, p = 9인 당근이 가장 맛이 좋다.
- 1 + 3 * 4 = 13
- 2 + 9 * 4 = 38
- 3 + 7 * 4 = 31
4일째에는 (5일째에 먹은 당근을 제외하고 남은) 두 당근 중에 w = 3, p = 7인 당근이 가장 맛이 좋다.
- 1 + 3 * 3 = 10
- 3 + 7 * 3 = 24
3일째에는 w = 1, p = 3인 당근이 가장 맛이 좋다. (1 + 3 * 2 = 7)
38 + 24 + 7 = 69이다.
구현할 때는 (w, p)를 리스트에 담아 정렬해서 맛을 구하면 된다.
w[i] < p[i]라는 조건이 있으므로 p를 기준으로 내림차순 정렬하면 된다.
만약 두 당근의 p 값이 같고 w 값이 다르더라도 뭘 먼저 계산하는지는 상관없다.
N <= T라는 조건이 있기 때문에 N개의 당근은 무조건 다 먹게 되고 모든 w 값은 결국 총합에 들어가게 된다.
그렇게 되면 p의 우선순위만 따져서 계산하면 된다.
정렬한 순서대로 맛 + 영양제 * 일수를 계산해서 총합을 구한다.
✏️ Solution
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
carrots = [tuple(map(int, input().split())) for _ in range(N)]
carrots.sort(key=lambda x: x[1], reverse=True)
total = 0
for i in range(N):
total += carrots[i][0] + carrots[i][1] * (T - i - 1)
print(total)