[BOJ 22981, Python 3] 휴먼 파이프라인

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

22981번: 휴먼 파이프라인

 

 

풀이

문제를 읽어보면 제일 느린 사람의 속도로 맞추기 때문에 v를 정렬하면 팀 한 개는 속도가 v[0]으로 확정되어 있습니다.

그리고 i != 0인 다른 속도 v[i]를 나머지 팀의 속도로 정해둔다고 가정하면 최대한 빠르게 옮기는 경우는 v[i]보다 속도가 빠른 n - i명의 사람들을 전부 v[i]가 속한 팀에 들어가는 것입니다.

v[0] <= v[i]이므로 속도가 빠른 곳에 인원을 최대한 배정하는 것이 빠르겠지요.

 

그러면 팀1과 팀2의 속도를 더하면 1분당 v[0] * i + v[i] * (n - i)만큼 속도를 낼 수 있으므로 저 값을 z라고 하여 k가 z에 나누어 떨어지면 답은 k // z이고, 나머지가 있으면 k // z + 1이 답이 됩니다. 그래서 v[i]를 하나씩 확인해보면서 나온 답중에 제일 작은 값을 찾아 출력하면 됩니다.

 

 

코드

n, k = map(int, input().split())
v = sorted([*map(int, input().split())])
ans = 1e18
for i in range(1, n):
    team1 = v[0] * i
    team2 = v[i] * (n - i)
    z = team1 + team2
    ans = min(ans, k // z if k % z == 0 else k // z + 1)
print(ans)