[ 백준 ] 2217 / 로프

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
58/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2217 / 로프
 *
 * Kind :: Greedy
 *
 * Insight
 * - 각 로프가 버틸 수 있는 최대 중량
 *   w1, w2, ..., w(N-1), wN
 *   + 오름차순으로 정렬
 *     s1, s2, ..., s(N-1), sN
 *     s1 이 버틸 수 있는 중량은 s1 뒤의 모든 로프들도 버틸 수 있다
 *     s2 가 버틸 수 있는 중량은 s2 뒤의 모든 로프들도 버틸 수 있다
 *     ...
 *     # 최대 중량이 가장 작은 s1 으로 버틸 수 있는 최대 중량은
 *       s1 과 그 뒤의 N-1 개의 로프를 이용하는 것으로
 *       s1 * N 이다
 *     # 최대 중량이 두번재로 작은 s2 로 버틸 수 있는 최대 중량은
 *       s2 와 그 뒤의 N-2 개의 로프를 이용하는 것으로
 *       s2 * (N-1) 이다
 *     # ...
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int W[N];
    for (int i=0; i<N; i++)
        cin >> W[i];

    // Process
    sort(W, W+N); /* 로프들이 버틸 수 있는 최대 중량을 오름차순으로 정렬 */
    int ans = -1;
    for (int i=0; i<N; i++) {
        /* 현재 로프가 버틸 수 있는 최대 중량 : W[i]
         * W[i] 를 버틸 수 있는 로프의 개수 : N-i */
        ans = max(ans, W[i]*(N-i));
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글