에베레스트 등반 |
---|
산이 높고 험하기로 유명한 에베레스트에는 N+1개의 베이스캠프가 있고, 산 아래부터 베이스캠프 0번, 베이스캠프 1번, ..., 베이스캠프 N번(에베레스트 정상)으로 정해진다. 베이스캠프 i-1번와 베이스캠프 i번 (1≦i≦N) 사이의 거리는 Di이다. 등반가인 준용이는 베이스캠프 0번에서 출발하여 캠프를 차례로 경유하여 베이스캠프 N번(에베레스트 정산)까지 등반하게 결심하였다. 베이스캠프 0번에서 베이스캠프 N(에베레스트 정산)까지 주어진 M시간 이내에 이동해야한다. 준용이는 베이스캠프에 머무는 매 시간마다 다음 두 가지 중 하나를 선택한다.
이동할 때마다 피로도가 쌓여 간다. 에베레스트에서는 매 시간마다 날씨변화가 나쁜 정도에 따라 이동에 어려움이 측정된다.(날씨가 나쁘면 수치는 커진다.) 준용이는 발달된 일기예보를 통해서 j시간(1≦j≦M)일 때 날씨로 인한 이동의 어려움이 Cj가 되는 것을 알고 있다. 만약 j시간일 때, 베이스캠프 i-1번에서 베이스캠프 i번으로 이동하는 경우, 피로도가 Di × Cj 만큼 쌓이게 된다. 하지만 이동하지 않고 기다리는 시간에는 피로도가 쌓이지 않는다. 준용이가 매 시간에 이동할지, 대기할지 잘 선택하여 가능한 피로도를 최소화하여 산 정상에 등극하고 싶다. 준용이가 M 시간 이내에 베이스캠프 N(에베레스트 정상)으로 이동할 때의 피로도 총합의 최소값을 구하라. |
입력 | |
---|---|
입력은 1 + N + M 행으로 구성된다. 첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ M ≦ 1000)가 공백을 구분으로 쓰여 있다. 이것은 에베레스트 산에는 N+1개의 베이스캠프가 있으며, 준용이가 베이스캠프 0번에서 베이스캠프 N번(산 정상)까지 M 시간 이내에 도착해야한다는 것을 의미한다. 다음 N 라인 중 i 번째 줄 (1 ≦ i ≦ N)에는 정수 Di (1 ≦ Di ≦ 1000)가 적혀있다. 이것은 베이스캠프 I-1번과 베이스캠프 i번 사이의 거리가 Di 임을 나타낸다. 다음 M 라인 중 j 번째 줄 (1 ≦ j ≦ M)에는 정수 Cj (1 ≦ Cj ≦ 1000)가 적혀있다. 이것은 j 일째 날씨로 인하여 이동의 어려움이 Cj 임을 나타낸다. |
출력 | |
---|---|
준용이가 M시간 이내에 도시 N으로 이동할 때의 피로도 총합의 최소값을 한 줄로 출력하라. |
예시 | |||
---|---|---|---|
1 | 입력 | 3 7 40 45 30 50 10 70 45 30 60 20 | |
출력 | 2350 |
출처 | |
---|---|
2017년 충북 정보올림피아드 지역예선 중등부 3번 |