๋ฌธ์
KSG ํธ์์ ์์๋ ๊ณผ์ผ์ฐ์ , ๋๋งํน์๊ตฌ๋ฅดํธ ๋ฑ์ ์ ์ ํ์ '2+1 ์ธ์ผ'ํ๋ ํ์ฌ๋ฅผ ํ๊ณ ์์ต๋๋ค. KSG ํธ์์ ์์ ์ ์ ํ 3๊ฐ๋ฅผ ํ ๋ฒ์ ์ฐ๋ค๋ฉด ๊ทธ์ค์์ ๊ฐ์ฅ ์ผ ๊ฒ์ ๋ฌด๋ฃ๋ก ์ง๋ถํ๊ณ ๋๋จธ์ง ๋ ๊ฐ์ ์ ํ ๊ฐ๊ฒฉ๋ง ์ง๋ถํ๋ฉด ๋ฉ๋๋ค. ํ ๋ฒ์ 3๊ฐ์ ์ ์ ํ์ ์ฌ์ง ์๋๋ค๋ฉด ํ ์ธ ์์ด ์ ๊ฐ๋ฅผ ์ง๋ถํด์ผ ํฉ๋๋ค.
์๋ฅผ ๋ค์ด, 7๊ฐ์ ์ ์ ํ์ด ์์ด์ ๊ฐ ์ ํ์ ๊ฐ๊ฒฉ์ด 10, 9, 4, 2, 6, 4, 3์ด๊ณ ์ฌํ์ด๊ฐ (10, 3, 2), (4, 6, 4), (9)๋ก ์ด 3๋ฒ์ ๊ฑธ์ณ์ ๋ฌผ๊ฑด์ ์ฐ๋ค๋ฉด ์ฒซ ๋ฒ์งธ ๊พธ๋ฌ๋ฏธ์์๋ 13์์, ๋ ๋ฒ์งธ ๊พธ๋ฌ๋ฏธ์์๋ 10์์, ์ธ ๋ฒ์งธ ๊พธ๋ฌ๋ฏธ์์๋ 9์์ ์ง๋ถํด์ผ ํฉ๋๋ค.
์ฌํ์ด๋ KSG ํธ์์ ์์ ์น๊ตฌ๋ค๊ณผ ๊ฐ์ด ๋จน์ ์ด Nํฉ์ ์ ์ ํ์ ๊ตฌ์
ํ๋ ค๊ณ ํฉ๋๋ค. ์ฌํ์ด๋ฅผ ๋์ ์ต์๋น์ฉ์ผ๋ก ์ ์ ํ์ ๊ตฌ์
ํ ์ ์๋๋ก ๋์์ฃผ์ธ์!
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ ์ ์ ํ์ ์ N (1 โค N โค 100,000)์ด ์ฃผ์ด์ง๋๋ค.
๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ ์ ํ์ ๊ฐ๊ฒฉ Ci(1 โค Ciโค 100,000)๊ฐ ์ฃผ์ด์ง๋๋ค.
์ถ๋ ฅ
์ฌํ์ด๊ฐ N๊ฐ์ ์ ์ ํ์ ๋ชจ๋ ์ด ๋ ํ์ํ ์ต์๋น์ฉ์ ์ถ๋ ฅํฉ๋๋ค. ์ ๋ต์ 231-1๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค.
ํ์ด
๋น์ผ๊ฑฐ๋ถํฐ ์ฐจ๋ก๋๋ก ๋๊ณ ์์์๋ถํฐ 3๊ฐ์ฉ ๋ฌถ์ผ๋ฉด ๋๋ค
์ ์ผ ๋น์ผ๊ฑฐ, ๊ทธ๋ค์ ๋น์ผ๊ฑฐ ์ง๋ถํ๊ณ ๊ทธ๋ค์ ๋น์ผ๊ฑธ ๊ณต์ง๋ก ์ป์ด๊ฐ๋ ํํ
๋ต์๋ 3์ ๋ฐฐ์๋ฒ์งธ (3์ผ๋ก ๋๋๊ธฐํ๋ฉด ๋๋จธ์ง๊ฐ 2์ธ ์ธ๋ฑ์ค) ๊ฐ๋ง ๋นผ๊ณ ๋ํ๋ฉด ๋จ
// ํ์ด : https://whkakrkr.tistory.com
#include <bits/stdc++.h>
using namespace std;
long long solution(int &n, vector<int>&c) {
long long ans = 0;
sort(c.begin(), c.end(), greater<>());
for(int i=0; i<n; i++) {
ans += i%3==2 ? 0 : c[i];
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int n;
cin >> n;
vector<int>v(n);
for(int i=0; i<n; i++) {
cin >> v[i];
}
cout << solution(n, v);
return 0;
}
'๐๏ธ ICPC Sinchon > Greedy' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 1931๋ฒ: ํ์์ค ๋ฐฐ์ (0) | 2025.03.18 |
---|---|
[BOJ][C++] ๋ฐฑ์ค 20115๋ฒ: ์๋์ง ๋๋งํฌ (Silver III) (0) | 2025.03.12 |
[BOJ][C++] ๋ฐฑ์ค 1758๋ฒ: ์๋ฐ์ ๊ฐํธ (Silver IV) (0) | 2025.03.12 |
[BOJ][C++] ๋ฐฑ์ค 1343๋ฒ: ํด๋ฆฌ์ค๋ฏธ๋ ธ (Silver V) (0) | 2025.03.10 |
[BOJ][C++] ๋ฐฑ์ค 14916๋ฒ: ๊ฑฐ์ค๋ฆ๋ (Silver V) (0) | 2025.03.10 |