[코딩테스트C++] 로프

오늘의 문제

로프

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 로프
bool cmp (int a, int b){
    return a>b;
}
int solution(vector<int> w){
    sort(w.begin(), w.end(), cmp);
    int answer = 0;
    for(int i=0;i<w.size();i++){
        if(w[i] * (i+1) > answer){
            answer = w[i] * (i+1);
        }
    }
    return answer;
}

풀이 법

• 가장 큰 중량을 담을 방법을 생각해보면 포함된 로프중 가장 작은 값과 포함된 로프의 개수를 곱한 값만큼의 중량을 감당할 수 있다.
• 그래서 가장 큰 값부터 포함된 개수를 곱하여 더 큰지 비교한다.
• sort를 안하면, 값이 뒤죽박죽이라 정확한 결과를 얻을 수 없다.
• 앞으로 나오는 값 중 더 큰 값이 없다는 가정이 있어야된다.

모범 답안

#include <cstdio>

char buf[1<<20];
int idx = 1<<20;

inline char read()
{
    if (idx == 1<<20) {
        fread(buf, 1, 1<<20, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt()
{
    int sum = 0;
    char now = read();
    
    while (now == ' ' || now == '\n') now = read();
    while (now >= '0' && now <= '9') {
        sum = sum*10 + now-48;
        now = read();
    }
    return sum;
}
int main()
{
	int n = readInt();
	
	int a[10001]{};
	for (int i = 0; i < n; ++i) a[readInt()]++;
	
	int ans = 0;
	for (int i = 0; i < 10001; ++i) {
        if (a[i] && ans < i*n) ans = i*n;
        n -= a[i];
	}
	
	printf("%d", ans);
	return 0;
}

배울 점

• 입력하는 부분이 되게 특이하다 템플릿으로 사용하나보다.