λ¬Έμ
μ€νλ°μ€λ μλμ μ
μ₯μν¬ λ λ
νΉν λ°©λ²μΌλ‘ μ
μ₯μν¨λ€.
μ€νλ°μ€μμλ μλμ 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;
}
'ποΈ ICPC Sinchon > Greedy' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ][C++] λ°±μ€ 20115λ²: μλμ§ λλ§ν¬ (Silver III) (0) | 2025.03.12 |
---|---|
[BOJ][C++] λ°±μ€ 11508λ²: 2+1 μΈμΌ (Silver IV) (0) | 2025.03.12 |
[BOJ][C++] λ°±μ€ 1343λ²: ν΄λ¦¬μ€λ―Έλ Έ (Silver V) (0) | 2025.03.10 |
[BOJ][C++] λ°±μ€ 14916λ²: κ±°μ€λ¦λ (Silver V) (0) | 2025.03.10 |
[BOJ][C++] λ°±μ€ 2109λ²: μνκ°μ° (Gold III) (0) | 2025.02.11 |