[파이썬] 백준 18234 : 당근훔쳐먹기 (골드3)

[파이썬] 백준 18234 : 당근훔쳐먹기 (골드3)

• https://www.acmicpc.net/problem/18124
  

---

풀이

방향성 생각

• 영양제가 항상 시작보다 크기때문에 최대한 오래 기다리는게 이득이다.
• 앞에서 부터 그리디하게 가져가면 당근이 온전하게 성장 불가능하다.
• 정렬 이후 뒤에서부터 접근한다.
• 맨 뒤에서 k일차에는 wi에 영양제가 (k-1)번 들어간 당근을 먹는다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N,T = map(int,input().split())
infos = [list(map(int,input().split())) for _ in range(N)]
infos.sort(key=lambda x:(x[1],x[0]))

eat,day = 0,1
while infos:
    carrot,energy = infos.pop()
    eat += carrot + energy*(T-day)
    day += 1
print(eat)

코멘트

• 테케에서 앞에서 부터 그리디하게 접근하면 틀린다고 보여줬기 때문에 나름 쉽게? 뒤에서 부터 확인함.
• 잘 알려진 발상이라 어렵지 않게 풀이. 난이도도 비슷하게 매겨진듯