68. C++ 백준 2217 로프 자세한 설명

안녕하세요 코딩하는 덕구입니다.

C++ 백준 2217 번 로프입니다.

그리디 알고리즘 문제입니다.

https://www.acmicpc.net/problem/2217

2217번: 로프

 

 

 

로프들을 이용해 들어올릴 수 있는 최대 중량을 구하는 문제이므로

만약 로프 3개가 주어진다면

로프 1개가 들어올릴 수 있는 최대 중량, 

로프 2개가 들어올릴 수 있는 최대 중량,

로프 3개가 들어올릴 수 있는 최대 중량을 비교해서 가장 높은 중량을 선택하면 되겠죠.

그럼 이 중량들은 어떻게 구하면 될까요?

 

로프 1개의 최대 중량은 로프들 중에 최대 중량이 가장 높은 로프를 선택하면 되겠죠.

로프 2개의 최대 중량은 로프들 중에 최대 중량이 가장 높은 순서대로 1번 로프, 2번 로프를 선택한 후

2번 로프의 최대 중량에 2를 곱하면 됩니다.

로프들 중에 가장 약한 로프가 버틸 수 있는 최대 중량까지 중량을 걸어야 최대 중량이기 때문이죠.

그럼 로프가 3개라면?

3개의 로프 중 가장 약한 로프가 버틸 수 있는 최대 중량 * 3을 해주면 됩니다.

 

i개라면?

i개 중 가장 약한 로프의 최대중량 * i가 되겠죠.

 

그럼 위의 직관을 가지고 코드를 구현해봅시다.

 

로프들을 배열 안에 저장한 후 내림차순으로 정렬합니다.

for(int i = 0; i<N; i++) cin >> ropes[i]; //로프 입력
sort(ropes, ropes+N, greater<int>()); //내림차순 정렬

각 로프의 개수마다 최대 중량을 저장할 배열 weights 입니다.

for(int i = 0; i<N; i++) weights[i] = ropes[i] * (i+1); //로프 개수별 최대 중량

ropes는 큰 수부터 작은 수 순서대로 정렬된 배열 이므로

ropes 안의 i번 째 로프는 i개의 로프 중 최대 중량이 가장 작은 로프가 되고,

i+1은 로프의 개수가 되므로 ropes[i] * (i+1)은

i+1개의 로프들을 이용한 최대 중량을 찾는 식이 됩니다.

이 값들을 로프들의 개수별 최대 중량을 저장할 weights 배열에 저장 한 후

가장 큰 값을 출력하면 답이 되겠죠

 

C++ 백준 2217 번 로프  최종 코드입니다.

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
int ropes[MAX] ={0,};
int weights[MAX] ={0,};

int main(){
    int N;
    cin >> N;
    for(int i = 0; i<N; i++) cin >> ropes[i]; //로프 입력
    sort(ropes, ropes+N, greater<int>()); //내림차순 정렬
    for(int i = 0; i<N; i++) weights[i] = ropes[i] * (i+1); //로프 개수별 최대 중량
    cout << *max_element(weights, weights+N); //최대 값 리턴 값 주소이므로 *연산

    return 0;
}

 

C++ 백준 2217 번 로프  자세한 설명이었습니다.

감사합니다.