오늘의 백준 - 2217번 : 로프 [C++]

문제

2217번: 로프 (acmicpc.net)

2217번: 로프

무콩🌱ver.

접근법

• 예제인 로프 2개, 각각의 중량은 10, 15로 생각해 보자.
  • 로프로 들 수 있는 경우
    • 1) 중량 15인 로프 하나로 들기 ==> 최대중량 15
    • 2) 중량 10으로 로프 2개로 들기 ==> 최대중량 20 ✔️최댓값
• 로프 3개 , 중량 10, 20, 30으로 생각해보자
  
  • 들 수 있는 경우
    • 1) 30짜리 1개로 들기 ==> 30
    • 2) 20짜리 2개로 들기 ==> 40 ✔️최댓값
    • 3) 10짜리 3개로 들기 ==> 30

결론 
1) 입력받는 중량 내림차순 정렬 (for문의 변수와 곱하는 개수를 맞추기 위해선 내림차순 정렬이 가장 적합함)
2) 들 수 있는 경우는 총 N번 
3) 비교 배열 = 중량 * 개수(내 중량보다 크거나 같은 중량의 개수)
4) 비교 배열에서 최댓값 구하여 출력

전체코드 : 무콩이🌱

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N; //줄 개수
	cin >> N;

	int* w = new int[N]; //버틸 수 있는 중량의 배열
	int* compare = new int[N+1]; //최대 중량 비교용 , 크기는 N+1임

	for (int i = 0; i < N; i++) {
		cin >> w[i]; //중량 N개만큼 입력받기
	}
	sort(w, w + N, greater<int>()); //중량 내림차순 정렬
	int max = 0;

	for (int i = 1; i < N+1; i++) { //1부터 시작해야함
		compare[i] = w[i - 1] * i; //i는 사용되는 로프의 개수 -> i=1 시작 이유
		if(compare[i] > max) max = compare[i];  // 최댓값 비교
	}
	cout << max;

	delete[] w;
	delete[] compare;
	return 0;
}