문제
연우에게는 방학 때 할 일이 산더미처럼 쌓여 있다.
그러나 연우는 너무 게을러서, 아무리 일이 많더라도 일을 특정 시간 이상 동안 하면, 반드시 쉬어줘야 한다.
그렇지만 이런 연우에게도 훌륭한 면이 있는데, 연우는 일단 한번 시작한 일은 끈기 있게 끝낸다는 것이다.
연우는 자기가 현재 하던 일을 완전히 끝내지 않으면 절대로 쉬거나 다른 일을 하지 않는다.
현재 연우에게는 N개의 할 일이 있다. 이 일들은 우선순위가 높은 순서대로 써 있으므로, 반드시 순서대로 해야 한다.
연우는 일을 시작하거나 마지막으로 쉰지 T분 이상이 지나면, B분동안 쉬어줘야 한다.
쉬지 않는다면, 어떤 일을 끝내고 다음 일을 시작하는데 걸리는 시간은 너무 미미하므로 없다고 가정한다.
연우는 자기가 모든 일을 끝내는데 걸리는 총 시간이 궁금하다. 여러분들의 목적은 연우가 모든 일을 끝내는 총 시간을 구하는 것이다.
예를 들어, 연우의 할 일이 표1과 같다고 하자. 할 일의 총 개수는 N=7개이며, 연우는 일을 시작하거나 마지막으로 쉰지 T=70분 이상의 할 일을 한 후에는 반드시 B=30분을 쉬어줘야 한다고 가정하자.
|
줄넘기 |
어머니 심부름 |
C++ 공부 |
정후네 집 방문 |
영어 단어 외우기 |
피아노 연습 |
수학 숙제 |
|
40분 |
30분 |
120분 |
50분 |
30분 |
40분 |
40분 |
표1
줄넘기와 어머니 심부름을 하면 총 70분동안 할 일을 했으므로, 연우는 30분동안 쉬어줘야 한다. 이 시점까지 총 70+30 = 100분의 시간이 지났다.
C++ 공부는 120분동안 해야 하는 긴 작업이다. 연우는 한번 한 일은 끝까지 끝내므로, C++공부를 끝내기 전 까지는 쉬지 않는다. 총 120분동안 끈기있게 공부를 끝낸 연우는 30분을 더 쉴 것이며, 지금까지 소요된 시간은 (앞의 100분) + (120+30)분 = 250분이다.
정후네 집 방문과 영어 단어 외우기는 합하여 (50+30)분의 시간이 소요된다. 영어 단어를 외우는 동안 연우의 인내력 한계치인 70분이 넘긴 하지만, 연우는 시작한 일은 반드시 끝내므로 영어 단어를 다 외우고 나서야 휴식을 취한다. 이 시점까지 걸린 시간은 (앞의 250분) + (50+30)분+30분 = 360분이다.
마지막으로 피아노 연습과 수학 숙제를 끝내면 360분+40분+40분 = 440분이다. 이 이후에는 쉬는 시간을 고려할 필요가 없으므로, 모든 일을 끝내는데 걸리는 시간은 440분이 된다.
연우의 스케쥴이 주어졌을 때, 연우가 모든 할 일을 끝내는데 걸리는 총 시간을 구하는 프로그램을 작성하시오.
입력
첫 줄에 N, T, B가 공백을 사이에 두고 주어진다.
N은 연우가 할 일의 총 수이며, T와 B는 연우가 T이상의 일을 하면 쉬는 시간 B를 가져야 한다는 의미이다.
둘째 줄에는 N개의 할 일들을 끝내는데 걸리는 시간인 t<sub>i</sub>가 공백을 사이에 두고 주어진다.
부분문제의 제약 형식
모든 부분문제에서 N≤50, T≤200, B≤200, t<sub>i</sub>≤200을 만족한다.
모든 입력값은 양의 정수이다.
부분문제 1) ( 1점) N=7, T=70, B=30이며, 연우가 할 일들의 목록은 문제 설명에 주어진 표1과 동일하다.
부분문제 2) (19점) t<sub>1</sub>+t<sub>2</sub>+…+t<sub>N</sub>(즉 모든 할 일들의 걸리는 시간의 합)은 T 이하이다.
부분문제 3) (33점) 모든 ti에 대해서 t<sub>i</sub>≥T를 만족한다.
부분문제 4) (57점) 주어진 제약조건 외에 아무 제약조건이 없다.
출력
첫 줄에 연우가 모든 할 일을 끝내는데 걸리는 총 시간을 출력한다.
예제
7 70 30
40 30 120 50 30 40 40
440
로그인해야 코드를 작성할 수 있어요.