[백준/c++] 11399번: ATM

 

 

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

11399번: ATM

 

ATM 1대, 사람 1~N명

 

값을 정렬하면 쉽게 해결되는 문제다. 

돈을 인출하는데 필요한 시간을 오름차순으로 정렬하면 걸리는 시간의 최솟값을 구할 수 있다.

memo라는 배열을 통해 앞 사람의 시간도 더하는 것을 구현해줬고, 이를 ans라는 변수에 넣어서 모든 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구해줬다. 

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1001];
int memo[1001], ans = 0;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> arr[i];
    sort(arr, arr+n+1);
    memo[0] = 0;
    for(int i=1; i<=n; i++){
        memo[i] = memo[i-1] + arr[i];
        ans += memo[i];
    }
    cout << ans << '\n';
    return 0;
}

 

사실 이렇게 말고도, 재귀함수를 통해서 값을 구할 수 있는데 이 경우, 당연히 메모리가 더 적게 든다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1001];
int ans = 0;

void rec(int k, int value){
    if(k == n+1){
        cout << ans << '\n';
        return;
     }
    
    ans += value;
    rec(k+1, value + arr[k+1]);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> arr[i];
    sort(arr, arr+n+1);
    rec(1, arr[1]);
    cout << ans << '\n';
    return 0;
}