백준 2217 - 로프 - 그리디 알고리즘

문제

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

풀이전략

1. 로프를 사용하여 들어올릴수 있는 무게의 최대값이다. 중요한 것은 로프마다 들어올릴수 있는 최대 중량을 넘어서면 안된다.
2. 따라서 로프들이 들어올릴수 있는 값이 큰 순으로 로프를 정렬하고, 이후 로프를 추가하는 것이 무게를 많이 들 수 있는지, 그냥 그대로 가는게 나은지를 계산해본다.

코드

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int N;
vector<int> rope;
bool mySort(const int& a, const int& b){
    return a>b;
}
int main(){

    // freopen("../input.txt","rt",stdin);
    scanf("%d",&N);
    int tmp;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        rope.push_back(tmp);
    }
    sort(rope.begin(), rope.end(), mySort);

    
    
    int res = 0;
    int resK = 0;
    for(int i=0; i<N; i++){

        // 이렇게 더 간단하게 깔끔하게 짤 수 있었다.        
        int w = rope[i] * (i+1);

        if(w > res){
            res = w;
        }

        /// 난 이렇게 할경우 1개만 찾고 끝난다
        // 따라서 이 코드에는 오류가 있다. 
        // if(w > res){
            
        //     res = w;
        //     resK++;
        // }
        // else break;
        
    }
    printf("%d\n",res);
    return 0;
}

소감

문제를 잘못풀어 한번 틀렸는데, 그 이유는 만약 10 4 4 4 4 4 4 4 일 때 분명 10 하나를 드는것이 4 두개를 드는것보다 크다. 하지만 10 하나를 드는것보단 4를 8번드는것이 값이 더 크다. 나는 괜히 효율성을 따진다고 break를 넣었다가 이 경우를 넣지 못했다. 이러한 실수를 하지 않도록 주의해야하고 또 이런 반례도 있다는 것을 잊지 말아야한다.