* 백준 2217번 - 로프

N개의 로프가 있다. N개의 로프는 각각 들 수 있는 최대중량이 존재한다. k개의 로프를 이용하면 중량을 k등분할 수 있다. 로프는 모두 사용하지 않아도 된다. 들 수 있는 최대중량을 구하시오.

# 틀린코드

처음에 바로 생각든 건 웬만하면 나눠드는게 이득이고 혼자드는게 이득인 걸 예외로 두자. 나눠드는 경우 로프중량값의 최솟값에 로프개수 N을 곱하면 최대중량이라고 생각하여 바로 코드를 신나게 적었다. 바로 틀림. why? 모든 로프를 사용하지 않아도 되는 경우가 있나보다.

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

div_weight = min(ropes)*N
solo_weight = max(ropes)

if div_weight > solo_weight:
  print(div_weight)
else:
  print(solo_weight)

# 시간초과코드

그래서 좀더 생각해보니 역순으로 정렬시킨 다음에 중량 잘치는 로프부터 개수를 늘려가면서 최대중량을 구하면 될 거라는 생각이 들었다. 이정도면 시간복잡도도 빠를거같은데? 라는 플래그를 세우며 시간초과가 발생했다. 알고보니 슬라이싱도 길게하면 꽤 느리다. 이 이상 어떻게 하지?

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

ropes.sort(reverse=True)
result = []
for i in range(2, N+1):
  result.append(ropes[0:i][i-1]*i)

print(max(result))

# 정답코드

여러번의 오류를 거쳐 다시 처음부터 생각해보았다. 들 수 있는 최대 중량을 구하라... 입력값을 역순으로 정렬하면 중량 제일 잘치는 로프 하나로 드는 경우도 계산한다. 나눠드는 경우만 생각하면 된다. 나눠들 때 최대 중량? 최소 중량 * N. 그럼 슬라이싱하고 인덱싱 할 필요없이 i번째가 가장 최솟값이 된다. 뭐야? 잘못된 방향으로 가면 이상한 부분에서 삽질하는 경우가 많은 것 같다.

import sys

input = sys.stdin.readline
N = int(input())
ropes = []
for i in range(N):
  ropes.append(int(input()))

ropes.sort(reverse=True)
result = []
for i in range(N): 
  result.append(ropes[i]*(i+1))

print(max(result))