[백준] 2217 로프 - Python

---

작년 11월 초부터 코테 스터디를 들어가게 되면서 파이썬으로 코테 문제를 꾸준히 문제를 풀기 시작했다. 실력이 이전보다 늘긴 했지만, 여태까지는 문제를 풀면서 내가 생각했던 내용들을 정리하지 않고 단순히 문제만 푸는 것에 급급했다. 어느 순간부터 더 이상 발전이 없는 느낌을 받았고, 공부 방식을 바꿔야겠다는 생각이 들었다.

따라서 내가 이 문제를 어떠한 방식으로, 어떻게 접근했는지 등의 과정을 글로 정리하면 나중에 비슷한 문제를 풀게 됐을 때 내가 어떠한 부분이 부족했는지 좀 더 쉽게 파악할 수 있고, 스스로 해결 과정을 정리해 나감으로써 한 번 더 내용을 상기시킬 수 있을 것이라는 생각이 들어 이 글을 기점으로 알고리즘 문제 풀이 블로그 작성을 시작하겠다.  

---

 

문제 설명 & 풀이

 

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

2217번: 로프

 

 

이 문제는 N(1 <= N <= 100,000) 개의 로프가 주어졌을 때, 이 로프들을 이용해 들어 올릴 수 있는 물체의 최대 중량을 구해내는 문제이다. 각 로프가 버틸 수 있는 최대 중량은 서로 다를 수 있고, 모든 로프를 사용해야 할 필요는 없다.

 

여기서 가장 중요한 내용은 k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에 모두 고르게 w/k만큼의 중량이 걸린다는 조건이다.

 

예제 1의 내용을 통해 문제를 분석해 보면 다음과 같다.

• 입력
  • 로프의 개수: 2개
  • 각 로프가 버틸 수 있는 최대 중량: 10, 15

 

• 출력
  • 20 (최대 중량이 10, 15인 로프를 이용해 들어 올릴 수 있는 물체의 최대 중량)

 

처음에는 어떻게 결과가 20이 나왔는지 이해가 되지 않았다.. 아까 말했듯 저 조건이 문제의 핵심이었다는 것을 알게 되었고, 이를 통해 문제를 해결할 수 있었다.

 

1. 처음에 중량이 10인 로프를 한 개 사용한다고 하면, 로프를 이용해 들어 올릴 수 있는 물체의 최대 중량은 10이 된다.
2. 남은 로프가 중량이 15인 로프 하나밖에 없기 때문에 총 두 개의 로프로 들어 올릴 수 있는 물체의 최대 중량은 20이 되고, 모든 로프를 다 사용했으므로 10과 20중 더 큰 값인 20이 정답이 된다.

여기서 25가 아닌, 20이 최대 중량이 되는 이유가 바로 k개의 로프를 사용해 중량이 w인 물체를 들어 올릴 때, 각각의 로프에 모두 고르게 k/w 만큼의 중량이 걸린다는 조건 때문이다.

반대로 각 로프에 15라는 중량이 걸리게 된다고 생각해 보자. 최대 중량이 10인 로프는 15보다 작기 때문에 중량을 버티지 못하고 끊어지게 된다.

따라서 둘 중 값이 더 작은 10이 k개의 로프에 걸려야 된다는 것을 알 수 있고, 현재 사용된 로프가 2개이므로 20이라는 결과가 나온다.

 

위에서 설명한 과정을 식으로 나타내면 다음과 같다.

물체의 최대 중량 = 병렬로 연결된 로프의 개수 * min(병렬로 연결된 로프의 중량)

 

이 문제는 그리디 알고리즘이라는 것을 알 수 있고, 풀이 과정은 다음과 같다.

 

1.  로프의 중량을 내림차순으로 정렬
2. 로프의 개수만큼 반복하며 위의 식을 이용해 물체의 최대 중량 계산
3. 계산된 중량 중 최대 값을 결과로 출력

 

중량을 내림차순으로 정렬하지 않고 오름차순으로 정렬하게 되면, 로프가 점점 추가될 때마다 계속해서 작은 로프의 중량이 병렬로 걸리게 된다. 따라서 내림차순으로 로프를 정렬하고, 로프를 병렬로 연결해 가며 물체의 최대 중량을 계산해야 하며, 이 중 가장 큰 값이 최종 결과가 된다.

 

 

소스 코드

 

파이썬으로 작성한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
rope = []
# 로프의 정보 차례대로 입력 받기
for i in range(n):
    rope.append(int(input()))

# 로프를 중량이 큰 것부터 내림차순 정렬
rope.sort(reverse=True)

# n번 반복하여 최대 중량 계산
result = []
for i in range(n):
    result.append((i+1) * rope[i]) # 현재 중량 계산

# 계산된 중량 중 가장 큰 값 출력
print(max(result))