[백준] 2217 - 로프 by C++

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

2217번: 로프

며칠전부터 반례를 잘못생각하고,

구현도 잘못하고 슬럼프인 것 같다.... 멍청해졌거나....

정말 쉽게 풀었던 기억이 나는데 이제와서 고민하고 있으니 가슴이 조금 아프다

 

알고리즘 방식

먼저 예시의 15 10 로프 2개를 사용해서 버틸 수 있는 최대 중량은

최대 중량이 낮은 로프가 버틸 수 있는 중량, 즉 10 * 2 = 20이다.

이를 일반화하면 내림차순으로 정렬된 수 n1, n2, n3...nk가 있을 때,

이 k개의 로프로 들어올릴 수 있는 최대중량은 nk * k이다.

(문제에서 요구하는 k개 중 선택이 아닌 모두 사용했을 때)

 

여기까지만 이해하면, nk * k의 값이 이전의 값보다 작아지는 순간에

루프를 끝내고 answer를 출력해도된다고 생각하겠지만,

아래와 같은 반례가 존재한다.

 

4개의 로프가 버틸 수 최대 중량이

15 10 6 6이라고 해보자.

an = nk * k이고,

a1 = 15 * 1 = 15

a2 = 10 * 2 = 20

a3 = 6 * 3 = 18

a4 = 6 * 4 = 24 이다.

앞서 말한 것처럼 작아지는 순간에 루프를 끝내게되면

a2 = 20이 출력되어 a4 = 24가 무시된다.

 

따라서 k의 범위는 1~k까지 모두 탐색해야 올바른 정답을 찾을 수 있다.

 

소스코드

 

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

using namespace std;

int N;
int answer;
vector<int> v;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	
	int buf;
	for (int i = 0; i < N; i++) {
		cin >> buf;
		v.push_back(buf);
	}

	//내림차순
	sort(v.begin(), v.end(), greater<>());

	for (int i = 0; i < N; i++) {
		int k = i + 1;
		if (v[i] * k > answer)
			answer = v[i] * k;

		//else
		//	break;
	}

	cout << answer;

}