[백준] 18234 - 당근 훔쳐 먹기 [Python(파이썬)]

문제

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

18234번: 당근 훔쳐 먹기

 

풀이

"당근을 먹지 않을 수도 있다"와 "항상 w<=p이다"라는 조건에 주목하여 정렬과 그리디로 풀 수 있는 문제였다. 항상 w<=p이기 때문에 w를 기준으로 오름차순 정렬을 한 후에 기다렸다가 최대한 늦게 수확함으로써 최댓값을 구할 수 있다. 즉, 당근을 안 먹고 기다렸다가 t-n일째 되는 날부터 수확을 시작하면 된다.

 

한 번에 아이디어를 떠올리긴 어려웠는데, 표를 그려보면 좀 더 쉽게 해결할 수 있는 문제였다.

 

코드

import sys

n, t = map(int, sys.stdin.readline().split())
carrots = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] # w(현재), p(증가)
carrots.sort(key = lambda x: x[1])

result = 0
feeded_days = t-n
for w, p in carrots:
    result += (w + p*feeded_days)
    feeded_days += 1

print(result)