BAEKJOON Algorithm

데하! 안녕하세요 DevStone입니다!

그리디 문제 일곱 번째 로프 문제입니다.

저 또한 공부하면서 포스팅하는 거라 제 알고리즘이 최적이거나

정답은 아닙니다! 단순히 참고 용도로 부탁드립니다.

처음에는 문제가 헷갈렸지만 핵심 문장은 "모든 로프를 사용해야 할 필요는 없으며"입니다.

예를 들어 버틸 수 있는 무개가 3인 로프 하나와 10인로프 하나가 있다면 3인로프 두 개를 사용하는 것보다

굳이 두 개의 로프를 사용하지 않고 두 번째 로프만 사용하는 것이 더 좋습니다.

따라서 로프의 길이를 내림차순으로 나열하고 N을 하나씩 증가시키며 곱하여 그중 가장 큰 값이

들 수 있는 최대 무개라는 걸 알 수 있습니다.

즉 (N번째 로프의 길이 * N) 이라는 식이 세워집니다.

2217번: 로프

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하

www.acmicpc.net

예제 소스는 git에서 확인하실 수 있습니다.

GitHub - Maker-Kim/Study

Contribute to Maker-Kim/Study development by creating an account on GitHub.

github.com

DevStone