1156번 - 장난감 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 264 | 36 | 25 | 24.272% |
문제
정문이는 생일을 맞아 $D$일동안 생일파티를 열기로 하였다. 이에 정문이 친구들은 시간을 내어 정문이 생일파티에 참석하기로 하였다. 그리고 정문이는 이번 생일파티는 친구들과 함께 장난감을 갖고 노는 것으로 시간을 보내기로 계획하였다. 좀 더 구체적으로 $i$번째 날에는 $T_i$개의 장난감을 갖고 놀기로 계획을 세웠다.
장난감 가게에는 장난감 하나를 $T_c$원에 판다. 정문이는 적당히 장난감을 사서 이 장난감들을 계속 재활용하여 파티를 하려고 했으나, 결벽증이 있는 친구들은 새 장난감이나 살균장에서 소독된 장난감이 아니면 안 갖고 놀겠다고 하는 탓에 어쩔 수 없이 계획을 수정하기로 하였다.
정문이가 이용하는 살균장은 두 곳이다. 한 곳은 밤에 장난감을 맡기면 $N_1$일이 지난 아침에 찾아올 수 있고 비용은 한 개당 $C_1$이 든다. 다른 한 곳은 마찬가지로 $N_2$일이 지난 아침에 찾아올 수 있고 비용은 한 개당 $C_2$가 든다.
문제는 정문이를 도와 적당히 장난감을 사고 적당히 이 장난감을 살균장에 맡기는 방식으로 생일파티를 끝낼 수 있는 최소 비용을 구하는 것이다.
입력
첫 줄에는 정수 $D$, $N_1$, $N_2$, $C_1$, $C_2$, $T_c$가 공백으로 구분되어 주어진다. 두 번째 줄에는 $D+1$번째 줄까지 $i+1$번째 줄에는 $i$번째 날에 필요한 장난감의 수가 주어진다.
출력
첫 줄에 생일파티를 끝내기 위한 최소비용을 출력한다.
제한
- $1 ≤ D ≤ 100\,000$
- $1 ≤ N_1, N_2 ≤ D$
- $1 ≤ C_1, C_2 ≤ 60$
- $1 ≤ T_c ≤ 60$
예제 입력 1
4 1 2 2 1 3 8 2 1 6
예제 출력 1
35
힌트
- Day 1 - 8개의 장난감을 \$24에 구입한다. 이 날 장난감을 모두 갖고 놀고 밤에 2개는 1번 살균장에 6개는 2번 살균장에 맡긴다.
- Day 2 - 아침에 어제 1번 살균장에 맡겼던 2개를 \$4원을 주고 찾아온다. 그리고 갖고 논 후 1개의 장난감을 2번 살균장에 맡긴다.
- Day 3 - 이틀 전 2번 살균장에 맡겼던 6개의 장난감을 \$6를 지불하고 찾아온다.
- Day 4 - 이틀 전 2번 살균장에 맡겼던 1개의 장난감을 \$1을 지불하고 찾아온다. 이로써 총 지불액은 $35가 된다.
※ Test case의 70%는 D가 500 이하이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호