[c++] 백준 11399: ATM

[c++] 백준 11399: ATM

🥈실버 4

https://www.acmicpc.net/problem/11399

11399번: ATM

---

 풀이1

P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우에서

줄을 [2, 5, 1, 4, 3]으로 세우면 각각의 값은 [1, 2, 3, 3, 4]이다.

이는 그냥 입력 받은 값을 오름차순으로 정렬하라는 것이다.

 

각 사람이 돈을 인출하는데 필요한 시간의 합은 다음과 같다.

1번사람: 1

2번사람: 1+2

3번사람: 1+2+3

4번사람: 1+2+3+3

5번사람: 1+2+3+3+4

오름차순 정렬한 값을 누적합을 통해 계산하고 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int arr[N];
  for (int i = 0 ; i < N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N);
  int cnt = 0, idx = 0, ans = 0;
  while (cnt < N) {
    idx = 0;
    while (idx <= cnt) {
      ans += arr[idx];
      idx++;
    }
    cnt++;
  }
  cout << ans;
  return 0;
}

 

풀이2

좀 더 그리디한 풀이 방법으로는 오름차순 정렬은 먼저 한다음 대기시간 반복수만큼 (n-i)를 추가하는 방법도 있다.

 

1번사람: 1

2번사람: 1+2

3번사람: 1+2+3

4번사람: 1+2+3+3

5번사람: 1+2+3+3+4

 

1은 5번, 2는 4번, 3은 3번, 그다음 3은 2번, 4는 1번 더해지게 된다.

따라서 각 요소는 맨 앞에 있을 경우 N번, 뒤로 갈수록 N-i번씩 더해진다는 규칙을 이용하면 누적합을 한 것과 똑같은 결과를 얻을 수 있는 것이다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int arr[N];
  for (int i = 0 ; i < N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += arr[i] * (N-i);
  }

  cout << ans;
  return 0;
}