[백준] 2217 - 로프 (다시풀기)

www.acmicpc.net/problem/2217

2217번: 로프

1차 풀이)

일단 예시답안 자체가 이해가 안됐다.. 그래서 검색해서 찾았을때, suri78.tistory.com/29 이 블로그 글이 가장 이해가 잘되어서 예제를 이해한 뒤 아이디어를 떠올렸다.

 

위 페이지에서의 로프가 버틸 수 있는 중량이 각각 rope1 : 10, rope2: 15 일때

rope1을 사용한다면 rope2도 버틸 수 있으므로 최대 20을 버틸 수 있음.

rope2를 사용한다면 rope1은 15을 버틸 수 없으므로 최대 15를 버틸 수 있음.

그러므로 이 두 로프를 사용했을 때 버틸 수 있는 최대값은 20

 

여기서 각각의 로프에서 버틸 수 있는 최대값을 구해서 그 중 최대값을 반환해야함을 알 수 있다.

그럼 최대값을 어떻게 구할까?

 

우선 내림차순으로 정렬한 후에

두번째로 중량이 큰 로프는 *2, 세번째는 *3...이런식으로 해서 곱한 것중 최대값이 로프 세개로 버틸 수 있는 중량의 최대값이다.

 

N = int(input())
rope_list = []
for i in range(N):
  rope_list.append(int(input()))

rope_list.sort(reverse=True) # 내림차순 정렬
answer = rope_list[0]

for i in range(N):
  if answer<rope_list[i]*(i+1):
    answer = rope_list[i]*(i+1)

print(answer)