ATM - 11399 (C++)

ATM

 

1. 문제

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는 데 걸리는 시간 P가 주어졌을 때, 각 사람이 돈을 인출하는데, 필요한 시간의 합의 최소값을 구하는 프로그램을 만들어야 한다.

2. 해설

정렬이 안된 경우와 오름차순으로 정렬된 경우를 비교하면 해답을 찾을 수 있다.

(1). 정렬이 안된 경우

5명의 사람일 때, 핵심은 정렬이 안된 배열일 경우인 [5, 1, 2, 3, 4]를 생각해 보면

1번 사람 -> 5 = 5분

2번 사람 -> 5 + 1 = 6분

3번 사람 -> 5 + 1 + 2 = 8분

4번 사람 -> 5 +1 + 2 + 3 = 11분

5번 사람 -> 5 + 1 + 2 + 3 + 4 = 15분

5 + 6 +8 + 11 + 15을 더하면 45분을 기다려야 한다.

(2). 오름차순으로 정렬된 경우

5명의 사람이 줄에 서 있을 때, 내림차순 정렬된 배열 [1, 2, 3, 4, 5]

1번 사람 -> 1 = 1분

2번 사람 -> 1 + 2 = 3분

3번 사람 -> 1 + 2 + 3 = 6분

4번 사람 -> 1 + 2 + 3 + 4 = 10분

5번 사람 -> 1 + 2 + 3 + 4 + 5 = 15분

1 + 3 + 6 + 10 + 15을 더하면 35분을 기다려야 한다.

(3). 결론

큰 수를 앞에 둘 경우, 각 사람이 돈을 인출하는데 필요한 시간이기에 각 사람마다 큰 수가 더해져 총합이 크게 나오게 된다.

따라서, 큰 수가 여러 번 더해지면 안 되기에 최솟값을 구해야 하기에 오름차순 정렬을 수행해야 한다.

3. 코드

#include <algorithm>
#include <iostream>
#include <vector>
#define MAX 1001
using namespace std;

int N;
vector<int> v;
int lines[MAX] = {
    0,
};
int main() {

  cin >> N;
  int tmp;
  // 입력
  for (int i = 0; i < N; i++) {
    cin >> tmp;
    v.push_back(tmp);
  }

  // 오름차순 정렬
  sort(v.begin(), v.end());

  int sum = 0;
  for (int i = 0; i < v.size(); i++) {
    sum += v[i];
    lines[i] = sum;
  }

  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += lines[i];
  }
  cout << ans;
}

 

 

감사합니다!

 

 

- 출처

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

11399번: ATM