[파이썬/python] 백준 - 18234 당근 훔쳐 먹기

문제

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

---

문제 설명

1. N 종류의 당근을 T일 동안 재배할 예정이다.
2. 각 당근은 w의 맛이 있고 p만큼 맛을 증가시켜주는 영양제가 당근 종류별로 T개씩 준비되어 있다.
   1. 영양제의 맛은 무조건 w보다 더 높다.
   2. 각 당근이 해당 위치에 심어져 있다면 영양제를 주고 없다면 당근을 심는다.
3. 토끼는 하루마다 당근을 훔쳐 먹는다.
4. 이 때 당근의 맛의 합을 최대로 하려고 한다. 최댓값을 구해라

 

---

풀이

이 문제의 핵심은 영양제에 있다.

영양제는 무조건 기존 당근의 맛보다 크니까 영양제를 넣고 당글을 먹는 것이 무조건 좋다.

즉, 영양제의 맛이 가장 높은 순, 기본 당근의 맛이 높은 순으로 정렬한 후 가장 많이 영양제를 먹은 순으로 그리디하게 당근을 먹게 했다.

 

1. 영양제, 당근의 맛 순서로 내림차순 정렬한다.
2. 가장 가치가 높은 당근부터 순서대로 당근을 먹는다. 
3. 결과를 출력한다.

---

코드

import sys
input = sys.stdin.readline

n,t = map(int,input().split())

c = [list(map(int,input().split())) for _ in range(n)]
c.sort(key = lambda x :(-x[1], -x[0]))

res = 0
for i in range(n):
    res += (c[i][0] + c[i][1]*(t-i-1))

print(res)

---

시간복잡도

• 정렬의 연산횟수는 $NlogN$
• N번만큼 당근을 먹으므로 $NlogN + N$
• 즉 시간복잡도는 약 $O(10**6)$이다.