빨래방 줄 세우기
문제
동네 빨래방에 세탁기가 한 대 있다. 지금 빨래 바구니를 든 N명이 모여 있다. 세탁기는 한 번에 한 사람의 빨래만 돌릴 수 있고, 한 사람의 빨래를 다 돌린 뒤에야 다음 사람의 빨래를 넣는다. 사람마다 빨래를 돌리는 데 걸리는 시간이 다르다.
어떤 사람이 기다린 시간은 자기 빨래가 끝날 때까지 걸린 시간이다. 즉 자기보다 앞선 사람들의 빨래 시간을 모두 더한 값에 자기 빨래 시간을 더한 값이다.
줄을 어떤 순서로 세우느냐에 따라 모든 사람이 기다린 시간의 합이 달라진다. 이 합을 가장 작게 만들려고 한다.
예를 들어 N=5명의 빨래 시간이 다음의 표와 같다고 해보자.
| 사람 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 빨래 시간 | 3 | 1 | 4 | 3 | 2 |
이 다섯 명을 2번, 5번, 1번, 4번, 3번 순서로 세웠다고 해보자. 각 사람이 기다린 시간은 다음과 같다.
| 줄 순서 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 사람 | 2 | 5 | 1 | 4 | 3 |
| 빨래 시간 | 1 | 2 | 3 | 3 | 4 |
| 기다린 시간 | 1 | 3 | 6 | 9 | 13 |
기다린 시간을 모두 더하면 1 + 3 + 6 + 9 + 13 = 32다. 이 순서가 합을 가장 작게 만드는 순서이므로 이 경우의 답은 32다.
줄을 거꾸로 세우면 합이 어떻게 달라지는지 보자. 같은 다섯 명을 3번, 1번, 4번, 5번, 2번 순서로 세우면 다음과 같다.
| 줄 순서 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 사람 | 3 | 1 | 4 | 5 | 2 |
| 빨래 시간 | 4 | 3 | 3 | 2 | 1 |
| 기다린 시간 | 4 | 7 | 10 | 12 | 13 |
이때 기다린 시간의 합은 4 + 7 + 10 + 12 + 13 = 46이다. 마지막 사람이 기다린 시간은 두 경우 모두 13으로 같다. 세탁기가 쉬지 않고 돌기 때문이다. 달라지는 것은 앞선 사람들이 기다린 시간이고, 그 때문에 합이 32에서 46으로 늘어난다.
N명의 빨래 시간이 주어졌을 때, 모든 사람이 기다린 시간의 합의 최솟값을 구하는 프로그램을 작성하여라.
N이 1,000명이고 모든 사람의 빨래 시간이 1,000분이면 답은 500,500,000이다. 이 값이 답의 최댓값이고 32비트 정수 범위 안에 들어가므로 수가 넘칠 걱정은 하지 않아도 된다.
입출력 예시
예시 1
입력
5 3 1 4 3 2
출력
32
예시 2
입력
1 606
출력
606
예시 3
입력
2 986 324
출력
1634
입력 조건
가장 먼저 첫째 줄에 빨래방에 모인 사람의 수 N이 주어진다. N은 1,000보다 작거나 같은 자연수다.
이어서 둘째 줄에 N명의 빨래 시간이 1번 사람부터 N번 사람까지 차례대로 공백 하나로 구분되어 주어진다. 각 빨래 시간은 1 이상 1,000 이하의 자연수다.
빨래 시간이 같은 사람이 여럿 있을 수 있다. 입력에 주어지는 순서는 줄을 세우는 순서와 아무 관계가 없다.
출력 조건
모든 사람이 기다린 시간의 합의 최솟값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 세탁기는 한 대뿐이고 한 번에 한 사람의 빨래만 돌립니다. 중간에 멈추고 다른 사람의 빨래를 끼워 넣을 수는 없습니다
- 어떤 사람이 기다린 시간에는 자기 빨래 시간도 들어갑니다
- 구하는 값은 한 사람이 기다린 시간이 아니라 N명이 기다린 시간을 모두 더한 값입니다
- 같은 빨래 시간을 가진 사람이 여럿 있을 수 있습니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1 606
606
2 986 324
1634
5 3 1 4 3 2
32
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.