๋ฌธ์
N(1 โค N โค 100,000)๊ฐ์ ๋กํ๊ฐ ์๋ค. ์ด ๋กํ๋ฅผ ์ด์ฉํ์ฌ ์ด๋ฐ ์ ๋ฐ ๋ฌผ์ฒด๋ฅผ ๋ค์ด์ฌ๋ฆด ์ ์๋ค. ๊ฐ๊ฐ์ ๋กํ๋ ๊ทธ ๊ตต๊ธฐ๋ ๊ธธ์ด๊ฐ ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ ๋ค ์ ์๋ ๋ฌผ์ฒด์ ์ค๋์ด ์๋ก ๋ค๋ฅผ ์๋ ์๋ค.
ํ์ง๋ง ์ฌ๋ฌ ๊ฐ์ ๋กํ๋ฅผ ๋ณ๋ ฌ๋ก ์ฐ๊ฒฐํ๋ฉด ๊ฐ๊ฐ์ ๋กํ์ ๊ฑธ๋ฆฌ๋ ์ค๋์ ๋๋ ์ ์๋ค. k๊ฐ์ ๋กํ๋ฅผ ์ฌ์ฉํ์ฌ ์ค๋์ด w์ธ ๋ฌผ์ฒด๋ฅผ ๋ค์ด์ฌ๋ฆด ๋, ๊ฐ๊ฐ์ ๋กํ์๋ ๋ชจ๋ ๊ณ ๋ฅด๊ฒ w/k ๋งํผ์ ์ค๋์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๊ฐ ๋กํ๋ค์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ด ๋กํ๋ค์ ์ด์ฉํ์ฌ ๋ค์ด์ฌ๋ฆด ์ ์๋ ๋ฌผ์ฒด์ ์ต๋ ์ค๋์ ๊ตฌํด๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ชจ๋ ๋กํ๋ฅผ ์ฌ์ฉํด์ผ ํ ํ์๋ ์์ผ๋ฉฐ, ์์๋ก ๋ช ๊ฐ์ ๋กํ๋ฅผ ๊ณจ๋ผ์ ์ฌ์ฉํด๋ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ๊ฐ ๋กํ๊ฐ ๋ฒํธ ์ ์๋ ์ต๋ ์ค๋์ด ์ฃผ์ด์ง๋ค. ์ด ๊ฐ์ 10,000์ ๋์ง ์๋ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ต์ ์ถ๋ ฅํ๋ค.
ํ์ด
๋กํ๋ฅผ n๊ฐ ์ฌ์ฉํ๋ค๊ณ ๊ฐ์ ํ๋ฉด ๊ฐ์ฅ ํ์ค์ด ์ ์ ๋กํ์ ํ์ค a*n์ ๋ฌด๊ฒ๋ฅผ ๋ฒํธ ์ ์๋ค
์๋ฅผ ๋ค์ด 10, 20, 30, 40์ ๋กํ๋ฅผ ์ฌ์ฉํ๋ค๋ฉด
1๊ฐ๋ง ์ฌ์ฉ -> 40 ํ๊ฐ -> 40 * 1 = 40
2๊ฐ๋ง ์ฌ์ฉ -> 40๊ณผ 30 -> 30*2 = 60
3๊ฐ๋ง ์ฌ์ฉ -> 40๊ณผ 30๊ณผ 20 -> 20*3 = 60
4๊ฐ ๋ค ์ฌ์ฉ -> 40๊ณผ 30๊ณผ 20๊ณผ 10 -> 10*4 = 40
์ด๋ฏ๋ก 2๊ฐ๋ 3๊ฐ๋ง ์ฌ์ฉํด์ผํ๋ ๊ฒ์ด๋ค
๋ฐ๋ผ์ ์ฃผ์ด์ง ๋กํ ์ค n๊ฐ ์ฌ์ฉ, n-1๊ฐ ์ฌ์ฉ, n-2๊ฐ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ๋ฅผ ๊ตฌํด์ ์ต๋๊ฐ์ ๊ตฌํ๋ฉด ๋๋ค
๋กํ๋ฅผ ํ์ค ์์๋๋ก ์ ๋ ฌํ ๋ค ๋ฐ๋ณต๋ฌธ์ ์ด์ฉํด์ ๊ฐ๋จํ๊ฒ ํ์ด๋ด์
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for(int i=0; i<n; i++) {
cin >> v[i];
}
int ans = 0;
sort(v.begin(), v.end());
for(int i=0; i<n; i++) {
ans = max(ans, v[i]*(n-i));
}
cout << ans;
}
2025.03.10
// ํ์ด : https://whkakrkr.tistory.com
#include <bits/stdc++.h>
using namespace std;
int solution(int &n, vector<int> &ropes) {
int ans = 0;
sort(ropes.begin(), ropes.end(), greater<>());
for(int i=0; i<n; i++) {
int cur = ropes[i];
int cnt = i+1;
ans = max(ans, cur*cnt);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int n;
cin >> n;
vector<int>ropes(n);
for(int i=0; i<n; i++) {
cin >> ropes[i];
}
cout << solution(n, ropes);
return 0;
}
'๐๏ธ ICPC Sinchon > Greedy' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 14908๋ฒ: ๊ตฌ๋ ์์ ๊ณต (Gold I) (0) | 2025.02.10 |
---|---|
[BOJ][Python / C++] ๋ฐฑ์ค 16953๋ฒ: A โ B (Silver II) (0) | 2024.11.01 |
[BOJ][C++] ๋ฐฑ์ค 16206๋ฒ: ๋กค์ผ์ดํฌ (0) | 2023.04.12 |
[BOJ][C++] ๋ฐฑ์ค 27112๋ฒ: ์๊ฐ ์ธ ๊ทผ๋ฌด ๋ฉ์ถฐ! (0) | 2023.02.01 |
[BOJ][C++] ๋ฐฑ์ค 11501๋ฒ: ์ฃผ์ (0) | 2023.01.31 |