[백준/C++] 1758번 알바생 강호

1.문제 링크

1758

2. 풀이 전 계획과 생각

• 그리디 알고리즘으로 풀기

3. 풀이

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

bool cmp(int i, int j){
    if(i>j)return true;
    else return false;
}

int main(){
    int n; cin>>n;
    int *arr = new int[n];
    
    // 입력
    for(int i=0;i<n;i++) cin>>arr[i];
    
    // 내림차순 정렬
    sort(arr,arr+n,cmp);
    
    ll tip=0;
    for(int i=0;i<n;i++){
        int temp=1L*arr[i]-(i+1-1);
        if(temp<0) continue;
        tip+=temp;
    }
    
    // 답 출력
    cout<<tip;
}

1. 입력 배열 내림차순 정렬

2. 돈 - (받은 등수 - 1)을 계산해 음수가 나오면 pass, 아니면 tip변수에 누적 저장

4. 풀이하면서 고민했던 점

• 정답 범위가 int형을 벗아나 long long형을 이용
• long long형에 정수를 저장할 때 1L*arr[i]-(i+1-1) 이런식으로 1L을 곱해주어 long long형으로 바꿔주어야 했음.

5. 문제를 풀고 알게된 개념 및 소감

• 그리디 알고리즘에 대한 이해도가 올라감.