๐Ÿ•๏ธ ICPC Sinchon/Greedy

[BOJ][C++] ๋ฐฑ์ค€ 11508๋ฒˆ: 2+1 ์„ธ์ผ (Silver IV)

์„ ๋‹ฌ 2025. 3. 12. 03:11
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ

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;
}
๋ฐ˜์‘ํ˜•