[백준 2217번] 로프 (C++)

1. 문제

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

2217번: 로프

 

2. 풀이

아이디어

완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다.

DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다.

따라서 더 빠른 풀이를 생각해야 한다. 그러므로 그리디를 한 번 의심해볼 수 있다.

 

다음 4개의 로프를 고려해보자.

4 1 3 5

위 중 3개로 중량을 만든다고 할 때 직관적으로 가장 큰 3개를 선택하는 것이 최선의 선택이라는 생각이 든다.

따라서 직관적으로  n개의 로프 중에서 k개를 선택할 때 "중량이 가장 큰 k개 로프를 선택할 때 최대가 전체 중량의 최대가 된다"는 결론을 얻을 수 있다.

직관을 확신으로 바꾸기 위해 증명해보자.

[증명]

n개의 로프 중에서 k개를 선택할 때 "중량이 가장 큰 k개 로프 말고도 최대가 되는 경우가 존재한다"라고 가정하자.

각각의 로프의 중량이 w(1) < w(2) <  ... < w(n)를 만족한다면

두가지 경우를 보자.

1. 중량이 가장 큰 k개의 로프를 선택한 경우
   w(n - (k - 1)) ~ w(n)을 선택하므로 들 수 있는 중량은 w(n-(k-1)) x k이다.
2. 중량이 가장 큰 k개 말고 다른 로프를 선택한 경우
   w(n- (k - 1))대신 w(n - (k -2))를 선택했다고 하면 중량은 w(n-(k-2)) x k이다.

이때 w(n-(k-1)) >  w(n-(k-2)) 이므로 어떤 경우에도 2의 경우가 1의 경우보다 클 수 없다.

따라서 가정에 모순이 생기므로 n개의 로프 중에서 k개를 선택할 때 "중량이 가장 큰 k개 로프를 선택할 때 최대가 전체 중량의 최대가 된다"는 결론을 얻을 수 있다.

이제 로프가 오름차순을 유지하도록 정렬한 후 1개부터 n개까지 고른 경우의 최댓값을 찾으면 된다.

 

알고리즘

[알고리즘 순서]

1. 로프를 오름차순 정렬한다.
2. 1개를 선택한 경우 ~ n개를 선택한 경우를 비교하며 최댓값을 갱신한다.

[구현]

#include<iostream>
#include<algorithm>

using namespace std;

int N, ans;
int rope[100000]; 
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> N;
    for(int i=0; i<N; i++) cin >> rope[i];
    sort(rope, rope + N);
    for(int i=0; i<N; i++){
        ans = max(ans, rope[i] * (N-i));
    }
    cout << ans;
    return 0;
}

[알고리즘 분석]

정렬 알고리즘은 보통 O(NlogN)의 시간 복잡도를 가지고 반복문으로 한번씩만 순회하므로 O(N + NlonN)의 시간 복잡도를 가진다. 따라서 1초 안에 충분이 해결할 수 있다.

 

3. 느낀점

그리디는 거의 정렬과 함께 나오는 것 같다. 그리디를 이용하여 풀 수 있는 간단한 문제였다. 그리디의 논리를 연습하기 좋은 문제이다.