๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 11399๋ฒˆ: ATM

by nitronium102 2022. 7. 1.
 

๋ฌธ์ œ

์ธํ•˜์€ํ–‰์—๋Š” ATM์ด 1๋Œ€๋ฐ–์— ์—†๋‹ค. ์ง€๊ธˆ ์ด ATM์•ž์— N๋ช…์˜ ์‚ฌ๋žŒ๋“ค์ด ์ค„์„ ์„œ์žˆ๋‹ค. ์‚ฌ๋žŒ์€ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ์œผ๋ฉฐ, i๋ฒˆ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ Pi๋ถ„์ด๋‹ค.

์‚ฌ๋žŒ๋“ค์ด ์ค„์„ ์„œ๋Š” ์ˆœ์„œ์— ๋”ฐ๋ผ์„œ, ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์ด ๋‹ฌ๋ผ์ง€๊ฒŒ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ด 5๋ช…์ด ์žˆ๊ณ , P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 ์ธ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ณด์ž. [1, 2, 3, 4, 5] ์ˆœ์„œ๋กœ ์ค„์„ ์„ ๋‹ค๋ฉด, 1๋ฒˆ ์‚ฌ๋žŒ์€ 3๋ถ„๋งŒ์— ๋ˆ์„ ๋ฝ‘์„ ์ˆ˜ ์žˆ๋‹ค. 2๋ฒˆ ์‚ฌ๋žŒ์€ 1๋ฒˆ ์‚ฌ๋žŒ์ด ๋ˆ์„ ๋ฝ‘์„ ๋•Œ ๊นŒ์ง€ ๊ธฐ๋‹ค๋ ค์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, 3+1 = 4๋ถ„์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. 3๋ฒˆ ์‚ฌ๋žŒ์€ 1๋ฒˆ, 2๋ฒˆ ์‚ฌ๋žŒ์ด ๋ˆ์„ ๋ฝ‘์„ ๋•Œ๊นŒ์ง€ ๊ธฐ๋‹ค๋ ค์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ์ด 3+1+4 = 8๋ถ„์ด ํ•„์š”ํ•˜๊ฒŒ ๋œ๋‹ค. 4๋ฒˆ ์‚ฌ๋žŒ์€ 3+1+4+3 = 11๋ถ„, 5๋ฒˆ ์‚ฌ๋žŒ์€ 3+1+4+3+2 = 13๋ถ„์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. ์ด ๊ฒฝ์šฐ์— ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์€ 3+4+8+11+13 = 39๋ถ„์ด ๋œ๋‹ค.

์ค„์„ [2, 5, 1, 4, 3] ์ˆœ์„œ๋กœ ์ค„์„ ์„œ๋ฉด, 2๋ฒˆ ์‚ฌ๋žŒ์€ 1๋ถ„๋งŒ์—, 5๋ฒˆ ์‚ฌ๋žŒ์€ 1+2 = 3๋ถ„, 1๋ฒˆ ์‚ฌ๋žŒ์€ 1+2+3 = 6๋ถ„, 4๋ฒˆ ์‚ฌ๋žŒ์€ 1+2+3+3 = 9๋ถ„, 3๋ฒˆ ์‚ฌ๋žŒ์€ 1+2+3+3+4 = 13๋ถ„์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์€ 1+3+6+9+13 = 32๋ถ„์ด๋‹ค. ์ด ๋ฐฉ๋ฒ•๋ณด๋‹ค ๋” ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์„ ์ตœ์†Œ๋กœ ๋งŒ๋“ค ์ˆ˜๋Š” ์—†๋‹ค.

์ค„์„ ์„œ ์žˆ๋Š” ์‚ฌ๋žŒ์˜ ์ˆ˜ N๊ณผ ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ Pi๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์‚ฌ๋žŒ์˜ ์ˆ˜ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ Pi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Pi ≤ 1,000)

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

ํ’€์ด

๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์ด ์ ์€ ์ˆœ์„œ๋Œ€๋กœ ๊ณ„์‚ฐํ•ด์ฃผ๋ฉด ๋œ๋‹ค. 

๋ฌธ์ œ๋Š” ๋ˆ ์ธ์ถœํ•˜๋Š” ์‹œ๊ฐ„์˜ ํ•ฉ์ธ๋ฐ ๋‘ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค. 

1. ์‹œ๊ฐ„๋ณต์žก๋„ O(n^2) : ๋ˆ„๊ตฌ๋‚˜ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•. 

2. ์‹œ๊ฐ„๋ณต์žก๋„ O(n) : ๊ฐ ์‹œ๊ฐ„์ด ๋‚˜์˜ค๋Š” ๋นˆ๋„๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉด ๋œ๋‹ค.

ex) time : 1 2 3 4 5 ๋ผ๊ณ  ํ•˜๋ฉด

์ฒซ ๋ฒˆ์งธ ์‚ฌ๋žŒ : 1

๋‘ ๋ฒˆ์งธ ์‚ฌ๋žŒ : 1 + 2

์„ธ ๋ฒˆ์งธ ์‚ฌ๋žŒ : 1 + 2 + 3

๋„ค ๋ฒˆ์งธ ์‚ฌ๋žŒ : 1 + 2 + 3 + 4

๋‹ค์„ฏ๋ฒˆ์งธ ์‚ฌ๋žŒ : 1 + 2 + 3 + 4 + 5

-> 1๋ถ„ * 5๋ฒˆ + 2๋ถ„ * 4๋ฒˆ + 3๋ถ„ * 3๋ฒˆ + 4๋ถ„ * 2๋ฒˆ + 5๋ถ„ * 1๋ฒˆ

-> ์ˆ˜์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด time[i] * (n-i)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;

    // ์ž…๋ ฅ
    cin >> n;
    vector<int> time(n, 0);
    for (int i=0; i<n; i++)
        cin >> time[i];

    // ์—ฐ์‚ฐ
    sort(time.begin(), time.end());

    // ์ถœ๋ ฅ (1)
    int result = 0, sum;
    for (int i=0; i<n; i++){
        sum = 0;
        for (int j=0; j<=i; j++)
            sum += time[j];
        result += sum;
    }

    // ์ถœ๋ ฅ (2) : ์‹œ๊ฐ„๋ณต์žก๋„ ๊ฐœ์„ 
    // (n-i)์„ ๋นˆ๋„๋กœ ์ƒ๊ฐ
    int result = 0;
    for (int i=0; i<n; i++)
        result += (time[i] * (n-i));

    cout << result;
}

๋Œ“๊ธ€