n 개의 로프를 가지고 있다고 하자. 우리는 이 로프를 이용해서 무거운 물체를 들기를 원한다.
로프별로 인장강도가 다르다. 인장강도 t 인 로프로 t 보다 더 무거운 물건을 들고자 하는 경우 로프는 끊어진다.
k 개의 로프를 가지고 w 인 물체를 들고자 하는 경우 k 개의 로프의 각각은 w/k 이상의 무게를 들어올릴 수 있는 인장강도가 되어야 한다. 그러나 로프 중에 w/k 보다 작은 인장강도가 있는 경우 줄은 끊어진다.
예를 들어, 세 개의 로프가 있고 각 인장 강도가 1 ,10 ,15 인 경우 무게가 3 보다 큰 물체는 들어올릴 수 없다. 3 보다 큰 물건을 들어올리는 경우 인장 강도 1 인 로프가 끊어진다.
그러나 두번째 로프 하나로도 10 까지는 들어올릴 수 있다.
n 개의 로프의 인장강도가 주어질 때 이 로프의 일부를 사용하여 가장 무거운 물체를 들어올릴 수 있는 무게를 찾는 것이 문제이다.
입력 3 10 1 15 출력 20 입력 2 10 15 출력 20
출처:Tehran 2003