요플레 공장 > 문제은행

본문 바로가기


알고리즘 그리디

2194 : 요플레 공장

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 687 회    시도횟수: 2369 회   



요플레 공장을 운영하시는 영휘의 아버지가 어머니와 함께 여행을 가신다. 그래서 영휘는 아버지를 대신해서 요플레 공장을 N주 동안 운영해야한다.

 

영휘가 걱정스러운 아버지는 영휘를 위해 N주 동안 필요한 우유의 양과 변동되는 가격을 미리 알아봐주었다.

 

아버지가 주신 정보에 의하면 각 주마다 우유는 1ℓ당 C원에 살 수 있고, 필요한 우유는 Yℓ이다. 또한 우유를 1주일 보관하는데 우유 1ℓ당 S원의 비용이 든다. 우유는 N주 동안 보관이 가능하며 우유 창고가 굉장히 커서 우유를 얼마든지 보관이 가능하다.

 

영휘는 아버지에게 칭찬을 받기 위해 N주 동안 최소의 비용으로 요플레 공장을 운영하고 싶어서 당신에게 도움을 청했다.

 

당신은 영휘에게 N주 동안 요플레 공장을 운영할 수 있는 최소비용을 구하여 주자.


첫 줄에 N과 S (1≤N≤10,000, 1≤S≤100)가 공백으로 구분되어 주어진다. 둘째 줄 부터 N+1번째 줄 까지 각 주의 C[i]와 Y[i] (1≤C[i]≤5,000, 0≤Y[i]≤10,000)가 주어진다. 각 주는 1주부터 순서대로 입력이 된다.



N주 동안 요플레 공장을 운영할 수 있는 최소비용을 출력한다.


[Copy]
4 5
88 200
89 400
97 300
91 500
[Copy]
126900



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.