백준 2217번 로프

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

최대 허용 중량이 w인 로프는 각각 하나씩 밖에 없으므로 그리디하게 접근할 수 있는 알고리즘 문제였습니다.

로프 중량을 오름차순으로 정렬한 뒤 (N-i+1)개를 병렬로 중첩하여 최대 중량을 찾아내는 식으로 접근하는 문제였습니다!

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

vector<long long> rope;

 

long long maxWeight(void)

{

        long long result = 0;

       

        //각각의 로프는 한 개씩만 존재하므로 그리디하게 접근

        for (int i = 0; i < N; i++)

        {

                 long long weight = rope[i];

 

                 //rope[i]를 병렬로 (N-i+1)개 겹쳤을 때 최대 중량

                 for (int j = i + 1; j < N; j++)

                         weight += rope[i];

 

                 result = max(result, weight);

        }

        return result;

}

 

int main(void)

{

        cin >> N;

       

        for (int i = 0; i < N; i++)

        {

                 int weight;

                 cin >> weight;

 

                 rope.push_back(weight);

        }

 

        sort(rope.begin(), rope.end()); //밧줄 정렬

 

        cout << maxWeight() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~