2217 로프

 

중량이 최소인 걸 찾아서 *n 을 하면 답이 아닐까? 싶었음

 

중량을 최대로 하려면 밧줄을 최대로 사용하는게 이득일거라 생각하고

최대로 쓴다면 밧줄 중 최소의 무게를 기준으로 한게 답이라 판단함

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", v[i]);

    int minv = *min_element(all(v));
    cout << minv;

    return 0;
}

 

ㅋㅋ 아 그런데 벡터 중 최소값을 찾는게 안됨

min()을 쓸 수 없길래 찾아보니 min_element()이고 이걸 쓰면 된다는데 비쥬얼스튜디오가 예외가 있다면서 자꾸 말린다

 

-> ㅋㅋㅋㅋㅋㅋ 이거 scanf 할 때 & 안 붙여서 문제였음

 

그러다 생각이 난건데 만약 밧줄이 150 10이라면 두 개를 안 쓰고 150 하나만 쓰는게 이득이네

 

그렇다면 밧줄을 정렬하고 어느 범위의 밧줄을 쓰면 될지 찾으면 될 것 같다.

 

150 130 20 10

 

이렇게 있다면 150 - 130까지 쓰면 이득이다! 판단하는거지

 

아 그런데 또 의문점이 생긴다 

 

150 20 이렇게 연속되지 않은 값을 쓸 수는 없을까? 

 

증명은 못하겠는데 아무리 생각해도 아닌 것 같음.. 그래서 원래 생각한대로 구현했고 맞았음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    sort(all(v), greater<int>());

    int max = 0;
    for (int i = 0; i < n; i++)
    {
        if (max < v[i] * (i + 1))
            max = v[i] * (i + 1);
    }

    cout << max << endl;

    return 0;
}

 

아! 증명 알겠음

 

밧줄 하나를 선택할 때 그 밧줄 기준으로 무게가 w/k씩 나눠지는데 이 때 최대한 많은 개수의 밧줄을 선택하는게 이득이다

 

그래서 150 130 20을 선택할 때 20을 선택한다면 밧줄이 많으면 좋으므로 150 130 20을 선택하는거지

 

와우!