[Python 알고리즘] 백준 2217번 : 로프

문제

• N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
• 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

입력

• 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

# Case 1
2
10
15

출력

• 첫째 줄에 답을 출력한다.

# Case 1
20

내가 제출한 풀이 - 틀림

import sys
import math

k = int(sys.stdin.readline().strip())
rope = [int(sys.stdin.readline().strip()) for _ in range(k)]
rope_sum = (sum(rope) // k) * k
rope_min = min(rope)
rope_max = max(rope)
res = 0

for i in range(rope_sum, rope_min - 1, -k):
    mok = math.ceil(i / k)
    is_ok = (True if mok <= rope_min else False)

    if is_ok:
        res = (rope_max if i <= rope_max else i)
        break

print(res)

나는 1개와 k개의 경우의 수만 봐와서 문제였던 것이다. 이번 문제는 어떻게 돌아가는지는 이해했지만 구현 자체를 잘못 했다고 봐도 무방하다...

정답

import sys

k = int(sys.stdin.readline().strip())
rope_list = [int(sys.stdin.readline().strip()) for _ in range(k)]
rope_list.sort(reverse=True)
res = []

for i in range(len(rope_list)):
    res.append(rope[i] * (i + 1))

print(max(res))

문제풀이

k : 3, rope_list : [12, 17, 19] 라고 가정을 해보자.

 

이 문장에 모든 답이 나와있었다.

•  k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

1. 19kg를 버티는 로프 1개를 거는 것보단 34kg(17kg + 17kg) / 2를 해서 19kg와 17kg로 17kg 2개를 버티는 게 낫다라는 뜻이다.
2. 12kg보단 19kg 하나를 버티는 게 낫고, 12kg + 17kg보단 17kg + 19kg가 더 잘 버틴다는 사실을 잘 알것이다. 이왕 적은 개수로 걸게 된다면 많은 중량을 견딜 수 있는 로프를 거는 게 낫다라는 뜻이다. 즉, rope_list를 내림차순으로 정렬해야한다.
3. 정렬된 rope_list는 [19, 17, 12]의 형태를 가지게 된다. 19kg를 버틸 수 있는 로프는 rope_list[0] = 19 밖에 없지만, 17kg를 버틸 수 있는 로프는 rope_list[0]과 rope_list[1]이 있다. 그렇다면 가장 적은 중량을 가진 로프(rope_list[n]) * 로프의 개수(k)를 하게 된다면 34kg를 버틸 수 있다는 결과가 나온다. 쉽게 말해 [19, 17] 중 중량을 버틸 수 있는 로프 중 가장 작은 것은 rope_list[1](17)이며, 19kg와 같이 나누어 들게 되니 19kg는 17kg를 들 수 있어 17 * 2 = 34가 된다. [17, 19]가 안 되는 이유는 17kg는 19kg를 버틸 수 없기 때문이다.
4. 마지막으로 [19, 17, 12]를 다 사용해 버틸 수 있는 무게는 몇인가?를 보면 된다. 12kg * 3 = 36kg라는 값이 나오게 된다. 그래서 36kg가 가장 많이 버틸 수 있는 무게이다.