백준 2217 - 로프(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2217

2217번: 로프

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

X개의 로프를 사용해 최대 중량을 구하는 문제입니다.

예를 들어 7, 10, 20를 버틸 수 있는 로프가 각각 있다고 가정하겠습니다.

이때 7을 이용해 만들 수 있는 중량은 7 * 3 = 21 입니다. 7을 10, 20 로프가 버틸 수 있기 때문입니다.

20을 이용한다면 20 * 1 = 20 입니다. 20은 7과 10 로프가 버틸 수 없기 때문입니다.

 

문제를 푸는 방법은 내림차순 정렬입니다.

그렇다면 20 10 7이 됩니다. 이때 20은 첫번째이니 20 * 1이 최대 중량, 10은 두번째이니 10 * 2가 최대중량이 됩니다.

따라서 해당 순서와 로프 중량을 곱한 값이 해당 로프의 최대 중량이 됩니다.

이를 구해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

int N;
vector<int> rope;

bool cmp(int a, int b) {
    if (a > b) return true;
    else return false;
}

void solve() {
    int maxi = 0;
    for (int i = 0; i < rope.size(); i++) {
        maxi = max(maxi, rope[i] * (i + 1));
    }
    cout << maxi;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        rope.push_back(x);
    }
    sort(rope.begin(), rope.end(), cmp);
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요