백준(Baekjoon Online Judge) - 2217번(로프) 문제 풀이

1. 문제

2. 입출력 예시

3. 문제 풀이

일단 이 문제는 여러 번 틀렸는데, 그 이유는 문제의 출제 의도를 잘못 파악했기 때문이었다. 처음에는 여러 개의 로프 중 하중이 가장 작은 로프에 로프의 수만큼 곱하면 되겠다라고 생각했다. 여러 번 제출을 시도하였으나, 전부 틀렸습니다 처리를 받고 문제를 차근차근 몇 번이고 다시 읽어보았다.

중량 w의 물체를 여러 다발의 로프에 걸었을 때 각각의 로프에 걸리는 중량은 w/로프의 수량 이다. 예를 들어서, 로프 3개의 하중이 각각[20, 50, 100]일 경우를 생각해보자. 먼저 하중이 20인 로프의 경우를 보면, 최대 20 × 3개 = 60 만큼 들 수 있다. 그 다음 하중이 50인 로프의 경우는 최대 50 × 2개(20 제외) = 100 만큼 들 수 있다. 하중이 100인 로프의 경우 최대 100 × 1개(20, 50 제외) = 100 만큼 들 수 있다. 즉, 무게 100이 주어졌을 때 로프 1개 또는 2개로 들어올릴 수 있으므로 최대 무게는 100이 된다.

위의 경우만 본다면 로프들 중 하중이 가장 큰 로프의 하중이 답이라고 착각할 수 있으니, 다른 경우를 생각해보자. 로프 3개의 하중이 각각 [20, 60, 100]에서 하중 20과 100인 로프의 경우는 위의 예시와 동일하다. 하중 60인 로프는 최대 60 × 2 = 120 만큼 들 수 있다. 즉, 무게 120이 주어졌을 때 로프 2개(60과 100)로 들어올릴 수 있으므로 최대 무게는 120이 된다.

이를 처리하는 코드를 작성하기 위해 먼저 아래와 같이 순서를 세워보았다.

• 로프의 수량 N 을 입력받는다.
• 로프의 수량만큼 해당 로프의 하중을 입력받고, 이를 리스트 변수(W)에 입력한다.
• 리스트의 요소를 내림차순으로 정렬한다.
• 빈 리스트를 생성 후 로프의 수량만큼 반복하며, 로프의 하중과 로프의 순서를 곱한 값을 빈 리스트에 추가한다. 즉, 위의 예시에서 나타낸 바와 같이 W[n-1] × n (단, 1 ≤ n ≤ N) 계산한다.
• 반복문이 종료된 후 리스트의 최댓값을 출력한다.

이를 코드로 나타내면 아래와 같다. 이 코드의 메모리는 36,428 KB, 시간은 4,428 ms가 소요되었다.

N = int(input())
W = [int(input()) for _ in range(N)]
W.sort(reverse=True)

lst = []

for n in range(1, N+1):
    lst.append(W[n-1]*n)

print(max(lst))

참고자료

• 백준알고리즘 문제 - 2217번 로프