[2217번] 로프

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘을 생각하면 쉽게 해결할 수 있다.

첫번째로 rope에 대한 길이 정보를 모두 rope배열에 받아낸다.

그리고 난 뒤, sort를 통해 내림차순(5,4,3,2,1 .. 방식)으로 정렬을 한다.

DP라는 배열에는 1번 배열부터 들어가게 되는데 DP[1]에는 rope[0]번 즉, 가장 긴 값 * 1이 되어

DP[1]에는 가장 긴 값의 rope길이가 들어갈 것이고

DP[2]에는 rope[1]*2가 될 것이다.

이 내용으로 눈치를 챌 수 있는 부분은 DP에 들어가는 값은 rope가 정렬이 되어있기에 

i+1개의 값중 가장 작은 값 * (i+1)을 하면 된다는 것이다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <algorithm> #include <cstdio>   using namespace std;   bool comp(const int &a, const int &b) {     return a > b; } int main() {     int n, k;     int rope[100010];     int DP[100020];       scanf("%d", &n);     for (int i = 0; i < n; i++)         scanf("%d", &rope[i]);       sort(rope, rope + n, comp);       for (int i = 0; i < n; i++)         DP[i+1] = rope[i] * (i+1);          sort(DP, DP + n + 1, comp);       printf("%d", DP[0]);     return 0; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus