[백준] 2217번 문제

www.acmicpc.net/problem/2217

2217번: 로프

문제는 잘 읽어보면 해결법이 보인다. 머리가 멍청한 건지... 문제를 이해하는데 5분이 걸렸다. ㅎㅎ

일단 이 로프 문제는 내 머리가 멍청함에도 불구하고 여러 번 읽어보고 직접 숫자를 적어보면서 이론적으로 이렇게 되겠다!! 라는 생각이 들어서 코드 작성 후에 검사를 했는데 역시 틀렸다.

잡소리는 그만하고 일단 문제를 풀면서 했었던 생각을 적어보겠다..

풀이 : 

입력 2

10 15
이 2개의 로프가 버틸 수 있는 최대 중량은 20이다.
하지만 10, 30이 된다면 그래도 똑같이 20일까? 30일 것 같다. 모든 로프를 사용할 필요는 없다고 했으니, 만약에 주어진 로프들의 최솟값을 기준으로 한 다음 그 값을 존재하는 로프들의 수만큼 곱한 값과 어떤 특정한 로프들의 크기를 비교 해서 두 수 중에서 더 큰 숫자를 고르면 된다.
문제의 해결법은 주어진 로프들을 이용해서 들어올릴 수 있는 물체의 최대 중량을 구해내면 된다. 모든 로프를 사용할 필요는 없다.
10 15 20 31 234 이런식으로 각 로프가 들어올릴 수 있는 무게가 주어졌다면, 답은 어떻게 될까?
10을 기준으로 5 X 10을 한다면 50이다. 그런데 답이 50일까? 아니다.
15를 기준으로 4 X 15를 하면 60이다. 저번보다 답이 커졌다. 그런데도 답이 아니다.
그렇다면 20을 기준으로 3 X 20을 하면 60이다. 답이 똑같다. 로프 수를 줄여나가는데도 값이 동등해지거나 더 커진다.
31을 기준으로 2 X 31을 하면 62이다. 이번에도 답이 커졌지만 답은 아니다.
이번에는 234를 기준으로 1 X 234를 하면 234다. 답이 맞다. 그러니까 '로프들'이 로프 하나로 바뀔 수 있는 것이다.

이 문제를 해결하기 위한 가장 중요한 핵심은 "정렬"이다. 정렬을 하지 않으면 문제가 어려워지게 된다.

어쨌든 정렬을 하게 되면 반복문을 돌면서 계산을 통해서 가장 큰 값만 찾으면 된다.

 

로프가 들 수 있는 최대 중량이 오름차순으로 정렬이 되면 반복문을 돌면서 "현재 위치에 있는 원소의 값"과 "접근해야할 원소들의 개수"를 곱한 값과 "이전의 최댓값"을 비교해주면서 반복문이 끝나면, 최종적으로는 "임의로 선택된 루프들이 버틸 수 있는 최대중량"이 나오는 것이다.

코드를 보면 이해가 될 것 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int n, i = 0, num;
	vector<int> v;
	cin >> n;
	while(i++ < n){
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	int res = 0;
	for (i = 0; i < n; i++) res = max(v[i] * (n - i), res);
	cout << res;
}

 

여태까지 많은 문제는 아니지만 계속 백준 문제를 풀다보니 약간의 문제 풀이에 도움이 되는 팁이 있다. 아무 문제나 들어가서 알고리즘 분류라는 카테고리를 보면 여러가지 방법으로 풀 수 있는데, 그 방법들 중에서 힌트가 되는 방법이 있으니 잘 보고 하면 된다.