πŸ•οΈ ICPC Sinchon/Greedy

[BOJ][C++] λ°±μ€€ 1758번: μ•Œλ°”μƒ κ°•ν˜Έ (Silver IV)

선달 2025. 3. 12. 02:48
λ°˜μ‘ν˜•

 

문제

μŠ€νƒ€λ°•μŠ€λŠ” μ†λ‹˜μ„ μž…μž₯μ‹œν‚¬ λ•Œ λ…νŠΉν•œ λ°©λ²•μœΌλ‘œ μž…μž₯μ‹œν‚¨λ‹€.
μŠ€νƒ€λ°•μŠ€μ—μ„œλŠ” μ†λ‹˜μ„ 8μ‹œκ°€ 될 λ•Œ κΉŒμ§€, λ¬Έμ•žμ— 쀄 μ„Έμ›Œ λ†“λŠ”λ‹€. 그리고 8μ‹œκ°€ λ˜λŠ” μˆœκ°„ μ†λ‹˜λ“€μ€ λͺ¨λ‘ μž…κ΅¬μ—μ„œ 컀피λ₯Ό ν•˜λ‚˜μ”© λ°›κ³ , 자리둜 κ°„λ‹€. κ°•ν˜ΈλŠ” μž…κ΅¬μ—μ„œ 컀피λ₯Ό ν•˜λ‚˜μ”© μ£ΌλŠ” 역할을 ν•œλ‹€.
μ†λ‹˜λ“€μ€ μž…κ΅¬μ— λ“€μ–΄κ°ˆ λ•Œ, κ°•ν˜Έμ—κ²Œ νŒμ„ μ€€λ‹€. μ†λ‹˜λ“€μ€ μžκΈ°κ°€ 컀피λ₯Ό λͺ‡ 번째 λ°›λŠ”지에 따라 νŒμ„ λ‹€λ₯Έ μ•‘μˆ˜λ‘œ κ°•ν˜Έμ—κ²Œ μ€€λ‹€. 각 μ†λ‹˜μ€ κ°•ν˜Έμ—κ²Œ μ›λž˜ μ£Όλ €κ³  μƒκ°ν–ˆλ˜ 돈 - (받은 λ“±μˆ˜ - 1) 만큼의 νŒμ„ κ°•ν˜Έμ—κ²Œ μ€€λ‹€. λ§Œμ•½, μœ„μ˜ μ‹μœΌλ‘œ λ‚˜μ˜¨ 값이 음수라면, κ°•ν˜ΈλŠ” νŒμ„ 받을 수 μ—†λ‹€.
예λ₯Ό λ“€μ–΄, λ―Όν˜ΈλŠ” νŒμ„ 3원 μ£Όλ €κ³  ν–ˆκ³ , μž¬ν•„μ΄λŠ” νŒμ„ 2원, μ£Όν˜„μ΄κ°€ νŒμ„ 1원 μ£Όλ €κ³  ν•œ 경우λ₯Ό μƒκ°ν•΄λ³΄μž.
민호, μž¬ν•„, μ£Όν˜„μ΄ μˆœμ„œλŒ€λ‘œ 쀄을 μ„œμžˆλ‹€λ©΄, λ―Όν˜ΈλŠ” κ°•ν˜Έμ—κ²Œ 3-(1-1) = 3원, μž¬ν•„μ΄λŠ” 2-(2-1) = 1원, μ£Όν˜„μ΄λŠ” 1-(3-1) = -1원을 팁으둜 주게 λœλ‹€. μ£Όν˜„μ΄λŠ” 음수이기 λ•Œλ¬Έμ—, κ°•ν˜Έμ—κ²Œ νŒμ„ 주지 μ•ŠλŠ”λ‹€. λ”°λΌμ„œ, κ°•ν˜ΈλŠ” νŒμ„ 3+1+0=4원을 λ°›κ²Œ λœλ‹€.
μŠ€νƒ€λ°•μŠ€ μ•žμ— μžˆλŠ” μ‚¬λžŒμ˜ 수 Nκ³Ό, 각 μ‚¬λžŒμ΄ μ£Όλ €κ³  μƒκ°ν•˜λŠ” 팁이 μ£Όμ–΄μ§ˆ λ•Œ, μ†λ‹˜μ˜ μˆœμ„œλ₯Ό 적절히 바꿨을 λ•Œ, κ°•ν˜Έκ°€ λ°›μ„ 수 μž‡λŠ” 팁의 μ΅œλŒ“κ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 μŠ€νƒ€λ°•μŠ€ μ•žμ— μ„œ μžˆλŠ” μ‚¬λžŒμ˜ 수 N이 주어진닀. N은 100,000보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜μ΄λ‹€. λ‘˜μ§Έ 쀄뢀터 총 N개의 쀄에 각 μ‚¬λžŒμ΄ μ£Όλ €κ³  ν•˜λŠ” 팁이 주어진닀. νŒμ€ 100,000보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜μ΄λ‹€.

좜λ ₯

κ°•ν˜Έκ°€ 받을 수 μžˆλŠ” 팁의 μ΅œλŒ“κ°’μ„ 좜λ ₯ν•œλ‹€.

 

풀이

λ’· μ†λ‹˜λ“€μ€ κΉŽμ΄λŠ” 팁이 크닀.

μ–΄μ°¨ν”Ό κΉŽμ—¬μ„œ μŒμˆ˜κ°€ λœλ‹€λ©΄ 많이 κΉŽμ΄λŠ” λ’€μͺ½μ— μž‘μ€ κΈˆμ•‘μ„ λ°°μΉ˜ν•˜λŠ”κ²Œ 이득이닀

 

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

long long solution(int &n, vector<int>tips) {
    long long ans = 0;
    
    sort(tips.begin(), tips.end(), greater<>());
    
    for(int i=0; i<n; i++) {
        int tip = tips[i] - i;
        ans += tip<0 ? 0 : tip;
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<int>tips(n);
	for(int i=0; i<n; i++) {
	    cin >> tips[i];
	}
	
	cout << solution(n, tips);
	
    return 0;
}
λ°˜μ‘ν˜•