[백준] 2217 - 로프

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

 

각자 들 수 있는 중량이 다른 로프 n개 중 여러개(모두 다 사용할 필요 없음)를 사용하여 최대 중량 값을 찾아내는 문제이다.

다만 k 만큼의 중량을 가진 물체를 로프 n개를 사용하여 들어올린다면, 각각의 로프에는 k/n만큼의 중량이 부여된다.

 

첫번째 시도에서는 모든 로프를 사용해야하는 줄 알고,

"므야 그냥 최소 값에 개수 곱하면 되는 거 아님??"

으로 접근했다가 문제를 다시 읽어보고 머쓱해졌다.

 

두번째 시도에서는 모든 로프를 내림차순으로 정렬한 후,

가장 큰 중량을 버틸 수 있는 로프보다, 더 큰 중량을 버틸 수 있는 순간이 오면 바로 출력하는 것으로 접근했다.

읽어보면 알겠지만 가장 큰 중량을 버틸 수 있는 로프도 함께 고려해야한다는 걸 간과하여 실패했다.

 

세번째 시도에서는 모든 로프를 오름차순으로 정렬한 후,

최소 중량을 하나씩 올려가며 최대 중량을 계산하면서, 최대 중량이 작아지는 순간에 바로 출력하였다.

이 경우, 최대 중량이 작아졌다가 다시 커질 수 있는 상황이 있을 수 있기 때문에 실패했다.

(thanks to GPT)

 

마지막 시도에서 이를 보안하여 문제를 해결하였다.

 

최종 코드는 다음과 같다.

https://github.com/csy-59/CodingTestPrac/tree/main/%EB%B0%B1%EC%A4%80/Silver/2217.%E2%80%85%EB%A1%9C%ED%94%84

CodingTestPrac/백준/Silver/2217. 로프 at main · csy-59/CodingTestPrac