백준 로프
-
[백준-2217]-[그리디알고리즘]-로프알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:54
문제링크 : https://www.acmicpc.net/problem/2217 이문제는 병렬로 연결된 로프가 버틸 수 있는 최대 중량이 얼마나 되는지 물어보는 문제이다. 로프가 한개일 때는 로프가 버틸 수 있는 한계가 최대 중량이다. 그럼 로프가 두개일 때는? 로프의 최대중량이 작은 로프의 힘 * 2 가 로프가 두개일때 최대 중량이다. 왜그럴까?? 문제에 다음 조건이 존재하기 때문이다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 중량이 20 일때 로프 두개를 사용하면 한 로프당 걸리는 중량은 10 이다. 최대중량이 10, 12 의 로프 두개가 있을때 최대 중량이 12인 로프가 아무리 10보다 더 들 수 있어도 그 이상의 무게를..