[백준/Python] #2217 : 로프 - 그리디

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

2217번: 로프

 

이 문제는 몇 번을 읽어봐도 뭔 말인지 이해가 안돼서

문제 이해하는 데에만 한참 걸렸다ㅋ.ㅋ.

 

 

 

---

문제 이해부터 먼저 해보자.

 

 

로프는 여러 개를 병렬로 사용할 수도 있고, 이 때 모든 로프를 사용할 필요가 없으며 몇 개를 골라서 사용해도 된다고 문제에서 알려줬다. 그리고 우리가 구해야 하는 건 로프를 전부 사용하든 몇 개를 골라서 사용하든, 하나를 사용하든 어쨋든 로프를 사용하여 할 수 있는 최대의 중량을 들어올리는 것이다.

 

 

예를 들어서

4개의 로프가 있고 각 로프가 들 수 있는 중량이 각각 10, 15, 40, 30 이라고 치자.

이 경우 중량 10을 로프 4개를 병렬로 연결하여 사용할 수 있다. 왜냐하면 4개의 로프 모두 10이상의 중량을 들어올릴 수 있기 때문이다.

아니면 중량 15를 로프 3개를 병렬로 연결하여 사용할 수도 있다. 첫번째 로프는 들어올릴 수 있는 중량이 10까지이므로 제외된다.

또 아니면 아예 중량이 40으로 가장 큰 로프 1개만 연결하여 사용할 수도 있다.

 

 

이를 정리해보면

우리가 로프를 임의로 선택하여 들어올릴 수 있는 중량의 경우의 수는

순서대로

10 + 10 + 10 + 10 = 40
15 + 15 + 15 = 45
40
30 + 30 = 60

이렇게 4가지이다.

 

그러면 최종적으로 우리는 이 중에 최대값을 구하면 되는 것이다.

 

 

즉, 각 로프가 들어올릴 수 있는 중량을 오름차순으로 정렬하여 (10, 15, 30, 40)

가장 작은 값은 전체 로프가 들어올릴 수 있는 중량이기 때문에 전체 로프의 개수(N)만큼 곱하면 되는 것이고,

그 다음으로 작은 값은 가장 작은 값 1개를 제외한 나머지 로프가 모두 들어올릴 수 있기 때문에 전체 로프의 개수 - 1 만큼(N - 1) 곱하면 된다.

그리고 마지막에 남은 가장 큰 값은 해당 로프 제외하고 나머지 로프가 전부 들어올릴 수 없는 중량이기 때문에 1을 곱해주면 된다.

 

이를 코드로 작성하면

N = int(input())
ropes = []
for _ in range(N):
	weight = int(input())
	ropes.append(weight)
ropes.sort()	# 10 15 30 40

for i in range(N):
	ropes[i] = ropes[i] * (N - i)
# 10 10 10 10 = 40 / 15 15 15 = 45 / 30 30 = 60 / 40
print(max(ropes))

  끝.

 

 

---

그리고 느낀 점이

사실 첨에 나는 입력받을 때 리스트 하나 만들고

각 로프 곱셈처리 해주고 나서 그 중에 max(리스트) 해서 최대값 구하려고 리스트 하나를 더 만들었었는데

누군가의 풀이를 보고 저런식으로 그냥 원래 만들었던 리스트에 요소 값들만 바꿔서 재활용하는 걸로 바꿨다.

하긴 쓸데없이 메모리를 낭비할 필요가 없겠다 싶어서

이럴 때는 머리를 이렇게 굴려볼 필요가 있겠다는 생각을 하게 되었음.

 

 

 

사실 그냥 내가 멍청해서 나만 문제 이해하기가 힘들었던걸 수도 있지만 ..

혹시나 어려움을 느낄 다른 분들을 위해 이번 문제는 한 번 자세히 정리해 보았습니다 !

도움이 됐으면 좋겠군요

 

그럼 20000