11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
N명의 사람이 줄을 서는데 순서대로 돈을 인출하는데 걸리는 시간이 주어집니다.
[1, 2, 3]의 순서대로 줄을 서고 인출하는데 걸리는 시간이 [a, b, c]라고 하면
1이 먼저 인출하면 2, 3은 a만큼의 시간을 기다리게 됩니다.
그 다음 2가 인출하면 3은 b만큼의 시간을 더 기다려서 총 a+b만큼을 기다립니다.
줄을 어떻게 서냐에 따라 총 기다리는 시간이 달라지는데, 이를 최소화하여 모든 사람이 돈을 인출하는데 필요한 시간을 최소로 해야합니다.
기다리는 시간을 최소로 하기 위해서는 인출하는 시간이 적은 사람이 먼저 하면 됩니다.
저는 인출하는 시간을 오름차순으로 정렬하였고, dp로 간단하게 구현하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[], dp[];
static int N, ans;
static void solve() {
for (int i = 1; i <= N; i++) {
dp[i] = dp[i - 1] + list[i];
ans += dp[i];
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N + 1];
dp = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(list);
}
public static void main(String[] args) throws Exception {
input();
solve();
}
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 8980 택배 (0) | 2021.02.16 |
|---|---|
| boj 11000 강의실 배정 (0) | 2021.02.16 |
| boj 1931 회의실 배정 (0) | 2021.02.16 |
| boj 2839 설탕 배달 (0) | 2021.02.16 |
| boj 1339 단어 수학 (0) | 2021.01.22 |