[BOJ] 백준_2217번_로프_C/C++백준 알고리즘2022. 1. 10. 14:37
목차
문제 출처
https://www.acmicpc.net/problem/2217
문제 설명
코드
//[BOJ] 2217번_로프
#include <iostream>
#include <algorithm>
using namespace std;
int cmp(int a, int b)
{
return b < a;
}
int main()
{
int n;
cin >> n;
int* w = new int[n];
int* rope = new int[n];
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
int maxV = w[0];
//큰 값 부터 우선적으로 계산하기 위해 내림차순 정렬
sort(w, w + n, cmp);
for (int r = 0; r < n; r++)
{
rope[r] = w[r] * (r + 1);
maxV = max(maxV, rope[r]);
}
cout << maxV << endl;
return 0;
}
풀이 과정
각 로프들이 들 수 있는 중량을 담은 배열 w을 내림차순으로 정렬한다. 내림차순으로 정렬하는 이유는 들 수 있는 중량 값이 가장 큰 로프부터 사용해야 최대 중량을 구할 수 있기 때문이다. 내림차순으로 정렬되었을 경우 로프를 1개만 사용할지부터 n개 전부를 사용할 지 결정할 수 있다. 1개만 사용할 경우 가장 중량이 큰 w[0]을 선택하게 된다. 최대 중량은 로프의 갯수가 많아질 수록 (각 로프들 중 들 수 있는 가장 작은 중량)x(로프의 수)로 구할 수 있으므로 로프 1개를 사용할 경우부터 n개를 사용할 경우까지 모든 경우의 최대 중량을 rope 배열에 담고 max함수를 이용해 최댓값을 구해 출력한다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_1049번_기타줄_C/C++ (2) | 2022.01.19 |
---|---|
[BOJ] 백준_2864번_5와 6의 차이_C/C++ (0) | 2022.01.12 |
[BOJ] 백준_1026번_보물_C/C++ (0) | 2022.01.08 |
[BOJ] 백준_11726번_2xn 타일_C/C++ (2) | 2021.12.30 |
[BOJ] 백준_23841번_데칼코마니_C/C++ (2) | 2021.12.26 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!