[BaekJoon 11399][⚪4] ATM

❓ 문제

백준 11399 - “ATM”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (그리디 + 정렬)

- 알고리즘

• Greedy, Sorting

- 설명

그리디 알고리즘과 정렬을 이용하는 풀이이다.

이 문제의 조건은 최소값을 구하는 문제이고 그 최소값을 구하는 방법이 명확하다. 전체 합은 이전까지의 값의 합에 현재값을 계속해서 더해가는 누적합 방식이므로, 결국은 큰 수가 앞에 있을수록 값이 커지게 된다. 이 점을 이용해서 sort를 이용해 오름차순으로 정렬을 하면, 최소값을 만드는 올바른 배열 순서가 만들어진다. 이 후에는 반복문을 돌며 누적값과 전체합을 구해주면 끝이다.

sort의 시간 복잡도가 가장 크므로 전체적인 시간 복잡도도 O(N log N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<int> vecTime(iN);
    for(int& iTime : vecTime)
    {
        cin >> iTime;
    }

    // 오름차순으로 정렬
    sort(vecTime.begin(), vecTime.end());

    long long iSum{};   // 전체 합
    long long iPref{};  // 누적 합
    for(int i = 0; i < iN; ++i)
    {
        iPref += 1LL * vecTime[i];  // 현재 값을 계속 더해줌으로써 누적합 갱신
        iSum += iPref;  // 누적합을 계속 더해줌으로써 전체합 갱신
    }

    cout << iSum;

    return 0;
}

---

💭 후기

좀만 생각해보면 알 수 있는 기본적인 그리디 알고리즘이 아닐까 싶다. 전체 합을 구하는 과정이 누적합 방식이고, 이 방식에서는 큰 값이 최대한 적게 반복될수록 최소값이라는 개념이 있으면 상당히 쉽게 풀 수 있는 문제이다.

참고로 모든 그리디가 DP로 치환될 수 있다는 것을 생각해 시도해봤지만, 줄에 서는 순서의 상태를 저장하고 모든 가능한 배열을 무식하게 돌면서 반복한다는 식의 로직의 복잡함과 비효율성 때문에, 안하는 것이 낫다고 생각하게 되었다.

🔗 참고자료

• 그리디