사막의 우물
문제
사막을 동서로 가로지르는 길 하나가 있고, 그 길 위에 우물이 N개 서 있다. 우물에는 서쪽 끝에서부터 1번, 2번, 차례대로 번호가 붙어 있으며 N번 우물이 동쪽 끝에 있다. 한 상인이 낙타를 끌고 1번 우물에서 출발해 N번 우물까지 가야 한다.
낙타는 물 한 통으로 정확히 1만큼의 거리를 간다. 그래서 어떤 구간을 지나려면 그 구간의 거리와 같은 수의 물통이 필요하다. 물은 우물에서만 살 수 있고, 물 한 통의 값은 우물마다 정해져 있다. 두 우물의 값이 같을 수도 있다. 낙타는 물통을 몇 개든 실을 수 있으므로, 값이 싼 우물에서 미리 많이 사 두었다가 나중에 쓸 수도 있다. 처음에 상인이 가진 물은 없다.
우물 사이의 거리와 우물마다의 물값이 주어졌을 때, 1번 우물에서 N번 우물까지 가는 데 드는 물값의 최솟값을 구하는 프로그램을 작성하여라.
예를 들어 N=4개의 우물이 있고, 각 우물에서 물 한 통을 사는 값이 다음의 표와 같다고 해보자.
| 우물 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 물 한 통 값 | 5 | 2 | 4 | 1 |
또한 이웃한 두 우물 사이의 거리가 다음의 표와 같다고 해보자. 구간은 서쪽부터 차례대로 N-1개 있다.
| 구간 | 1번과 2번 사이 | 2번과 3번 사이 | 3번과 4번 사이 |
|---|---|---|---|
| 거리 | 2 | 3 | 1 |
어떤 구간을 지날 물은 그 구간보다 서쪽에 있는 우물에서만 살 수 있다. 그래서 각 구간에 쓸 물은 그 구간까지 지나온 우물 가운데 값이 가장 싼 곳에서 사면 된다. 구간마다 그렇게 계산한 결과는 다음과 같다.
| 구간 | 1번과 2번 사이 | 2번과 3번 사이 | 3번과 4번 사이 |
|---|---|---|---|
| 거리 | 2 | 3 | 1 |
| 지나온 우물 중 가장 싼 값 | 5 | 2 | 2 |
| 드는 물값 | 10 | 6 | 2 |
세 구간의 물값을 더하면 18이므로 현재 예시에서 정답은 18이다. 3번 우물의 값은 4이지만 2번 우물의 값이 2이므로, 3번과 4번 사이를 지날 물도 2번 우물에서 미리 사 두는 쪽이 싸다. 4번 우물의 값은 1로 가장 싸지만 그곳에 닿으면 길이 끝나므로 쓸 자리가 없다.
거리와 물값이 각각 최대 1,000,000,000이고 구간이 최대 99,999개이므로 답은 1,000,000,000,000,000,000보다 커질 수 있다. 수가 넘치지 않도록 큰 정수를 다룰 수 있는 방법으로 더해야 한다.
입출력 예시
예시 1
입력
4 2 3 1 5 2 4 1
출력
18
예시 2
입력
2 454 381 461
출력
172974
예시 3
입력
5 149 237 865 457 123 295 3 429 312
출력
51444
입력 조건
가장 먼저 우물의 수 N이 첫째 줄에 주어진다. N은 2 이상 100,000 이하의 자연수다.
이어서 둘째 줄에 이웃한 두 우물 사이의 거리가 서쪽부터 차례대로 N-1개 공백 하나로 구분되어 주어진다. 각 거리는 1 이상 1,000,000,000 이하의 자연수다.
이어서 셋째 줄에 각 우물에서 물 한 통을 사는 값이 1번 우물부터 N번 우물까지 차례대로 N개 공백 하나로 구분되어 주어진다. 각 값은 1 이상 1,000,000,000 이하의 자연수다.
출력 조건
1번 우물에서 N번 우물까지 가는 데 드는 물값의 최솟값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 거리는 N-1개, 물값은 N개 주어집니다. 두 줄의 수 개수가 다른 점에 주의하십시오
- 어떤 구간에 쓸 물은 그 구간보다 서쪽에 있는 우물에서 사야 합니다
- 물통을 실을 수 있는 개수에 제한은 없습니다. 싼 우물에서 미리 많이 사 두어도 됩니다
- 답이 2의 53제곱을 넘을 수 있으므로 배정밀도 실수로 더하면 값이 어긋납니다. 큰 정수를 다룰 수 있는 방법을 쓰십시오
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 454 381 461
172974
5 149 237 865 457 123 295 3 429 312
51444
4 2 3 1 5 2 4 1
18
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.