[BOJ] 2217번: 로프

문제

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

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

입출력 예시

 

풀이

풀고 나서 바로 정리했어야 하는데 시간이 좀 지나서 그 당시 이해했던 걸 제대로 적을 수 있을지 모르겠다. 일단 문제 이해에 도움을 줬던 연구실 친구들에게 무한한 감사를!

 

아이디어 ☝

일단 내가 처음에 생각했던 건 '버틸 수 있는 중량이 가장 적은 로프를 기준으로 삼아서 그 로프를 k개 쓰는 것'이었다. 그래서 코드로도 min(ropes)*K가 끝이었는데 4%에서 틀렸다. 친구랑 같이 고민하고 있었는데 친구가 찾아준 반례는 'K=3, 5 10 20'이 입력으로 들어오는 경우였다.

 

저렇게 입력이 들어오면 20을 버틸 수 있는 로프 한 개만 쓰는 경우가 들어올릴 수 있는 물체의 최대 중량이기 때문에 답이 20이 되어야 한다. 하지만? 내 방식대로라면 15가 최대라서 바로 오답이 되어 버리는 것!

 

그래서 첫 방식에서 'K를 곱해줘버리면 무조건 모든 로프를 쓰는 경우가 되기 때문에 모든 로프를 쓰지 않고도 최대 중량을 들어올릴 수 있는 경우를 생각하지 못하므로 이 방법은 허점이 있다'는 결론을 내렸다.

 

아이디어 ✌

'물체를 들어올릴 때 가장 약한 로프의 한계를 초과하지 않으면서 최대한 많은 중량을 들어올릴 수 있게 하는 것'이 핵심이라고 할 수 있다.

 

위의 과정을 구현하기 위해 버틸 수 있는 중량이 무거운 순으로 정렬하고 정렬된 로프들을 순회하면서 각 로프를 포함하여 그 이하의 로프들만 사용했을 때 들어올릴 수 있는 최대 중량을 계산해준다.

 

5, 10, 20이 입력으로 들어왔다치고 정리를 해보자.

 

1) 배열 정렬 → ropes = [20, 10, 5]

2) 로프 1개 → 20짜리 하나만 쓰면 되기 때문에 20이 최대 → ropes[0]*1

3) 로프 2개 → 20짜리 하나, 10짜리 하나를 쓰되 버틸 수 있는 중량이 가장 적은 10이 기준이라 20이 최대 → ropes[1]*2

4) 로프 3개 → 20짜리 하나, 10짜리 하나, 5짜리 하나를 쓰되 5가 기준이라 15가 최대 → ropes[2]*3

 

 

저 내용을 그대로 구현하는 건 어렵지 않기 때문에 코드 삽입은 생략한다. 근데 뭔가 해석이 깔끔하지 않은 느낌이라 찝찝 😐