λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 11399번 : ATM

by nitronium102 2021. 8. 16.

문제

μΈν•˜μ€ν–‰μ—λŠ” 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뢄이닀. 이 방법보닀 더 ν•„μš”ν•œ μ‹œκ°„μ˜ 합을 μ΅œμ†Œλ‘œ λ§Œλ“€ μˆ˜λŠ” μ—†λ‹€.

-> λΆ„μœΌλ‘œ 따지면 [1, 2, 3, 3, 4]이닀. μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬ν•˜λΌλŠ” 말!

쀄을 μ„œ μžˆλŠ” μ‚¬λžŒμ˜ 수 Nκ³Ό 각 μ‚¬λžŒμ΄ λˆμ„ μΈμΆœν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„ Piκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, 각 μ‚¬λžŒμ΄ λˆμ„ μΈμΆœν•˜λŠ”λ° ν•„μš”ν•œ μ‹œκ°„μ˜ ν•©μ˜ μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 μ‚¬λžŒμ˜ 수 N(1 ≤ N ≤ 1,000)이 주어진닀. λ‘˜μ§Έ μ€„μ—λŠ” 각 μ‚¬λžŒμ΄ λˆμ„ μΈμΆœν•˜λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„ Piκ°€ 주어진닀. (1 ≤ Pi ≤ 1,000)

좜λ ₯

첫째 쀄에 κ° μ‚¬λžŒμ΄ λˆμ„ μΈμΆœν•˜λŠ”λ° ν•„μš”ν•œ μ‹œκ°„μ˜ ν•©μ˜ μ΅œμ†Ÿκ°’μ„ 좜λ ₯ν•œλ‹€.

풀이

그리디 μ•Œκ³ λ¦¬μ¦˜μ„ ν™œμš©ν•˜λŠ” 문제

μœ„μ—μ„œ μ–˜κΈ°ν–ˆλ“― μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬ν•˜μ—¬ ν’€λ©΄ λœλ‹€. 

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

int main(){
  int N, P, total=0, time=0;
  cin >> N;
  vector<int> v;
  for (int i=0; i<N; i++){
    cin >> P;
    v.push_back(P);
  }

  // μ˜€λ¦„μ°¨μˆœ μ •λ ¬
  sort(v.begin(), v.end());

  // μ΅œμ†Ÿκ°’ κ΅¬ν•˜κΈ°
  for (int i=0; i<N; i++){
    total += time[i]*(n-i);
  }
  cout << total;
}

 


SORT λ‚΄λ¦Όμ°¨μˆœμœΌλ‘œ μ •λ ¬ν•˜λŠ” 방법

1. reverse 반볡자인 rbegin, rend 이용

sort(v.rbegin(), v.rend());

2. greaterλ₯Ό μ‚¬μš©ν•˜μ—¬μ„œ λ‚΄λ¦Όμ°¨μˆœ. lessλŠ” μ˜€λ¦„μ°¨μˆœ

sort(v.begin(), v.end(), greater<int>());

3 λžŒλ‹€ λ°©μ‹μœΌλ‘œ μž‘μ„±(μ•„λž˜ ν•¨μˆ˜λ‘œ μž„μ˜ 순으둜 μ •λ ¬ 방식과 동일)

sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

 

λŒ“κΈ€