[코테/백준] Python 로프 - 2217번

실패 | 시도 6번

 

🔗 [백준] 2217번 로프

2217 : [그리디 알고리즘] 로프(py)

---

문제 설명

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

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

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

---

문제 분석

- 로프에 모두 고르게 w/k 만큼의 중량이 걸리기 때문에 견딜 수 있는 중량이 가장 적은 로프를 기준으로 최대 중량을 구해야 한다. 또 로프를 다 사용할 필요가 없기 때문에 일부 로프를 사용했을때 최대 중량을 들 수 있는 로프들을 선택해야 한다. 

- 견딜 수 있는 중량 로프를 내림차순으로 정렬하고 끈의 개수를 점차 늘려준다.

예) 로프 3개 : 100, 70, 5

• w / k = 최대 중량(w') → w = k * 최대 중량(w') 
• 100 (1개) : 100 * 1 = 100
• 100, 70 (2개) : 70 * 2 = 140
• 100, 70, 5 (3개) : 5 * 3 = 15

→ 100, 70 (2개) 로프를 사용할 때 최대로 들 수 있는 중량(w)은 140이다. 

---

입력

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

---

출력

첫째 줄에 답을 출력한다.

---

입력과 출력 예시

입력	출력
2 10 15	20

 

---

내 소스

• 첫시도 : 실패 (시간 부족)

n = int(input())
rope_weights = []
for _ in range(n):
    rope_weights.append(int(input()))
rope_weights.sort(reverse=True)

maximum = 0
for i in range(n):
    if maximum <= rope_weights[i] * (i+1) :
        maximum = rope_weights[i] * (i+1)
print(maximum)

 

소스 설명

n = int(input())
rope_weights = []
for _ in range(n):
    rope_weights.append(int(input()))
rope_weights.sort(reverse=True)

[1 - 5] : 각 로프가 버틸 수 있는 최대 중량을 리스트에 넣고 내림차순으로 정렬한다.

 

maximum = 0
for i in range(n):
    if maximum <= rope_weights[i] * (i+1) :
        maximum = rope_weights[i] * (i+1)

[7 - 10] : 각 로프가 버틸 수 있는 최대 중량과 로프 개수를 곱한 값이 maximum보다 크면 maximum 변수에 저장한다.

---

다른 코드 분석

- 로프의 최대 중량과 로프 개수를 곱해서 리스트에 넣고 max() 함수를 이용해서 최대로 들 수 있는 중량을 구했다.  

---

Ref. 

1. 문제 풀이 / https://jitolit.tistory.com/134

2. 문제 풀이 / https://covenant.tistory.com/128

3. 문제 풀이 / https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2217%EB%B2%88-%EB%A1%9C%ED%94%84-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀