Softeer [Level 3] 슈퍼컴퓨터 클러스터 {언어 : Python}

알고리즘

Softeer [Level 3] 슈퍼컴퓨터 클러스터 {언어 : Python}

스위태니 2024. 3. 8. 00:10

728x90

문제 링크

https://softeer.ai/practice/6252

Softeer - 현대자동차그룹 SW인재확보플랫폼

softeer.ai

정답 코드

import sys
N, B = map(int, input().split())
computers = sorted(list(map(int, input().split())))

left = 1
right = 2000000000

minV = 2000000000

while left <= right:
    mid = (left + right) // 2
    currentMoney = B
    for com in computers:
        if com < mid:
            cost = (mid - com) ** 2
            if cost > currentMoney:
                right = mid - 1
                break
            currentMoney -= cost
    else:
        left = mid + 1

print(right)

풀이 방법

찾으려고 하는 값(mid)이 최저성능의 컴퓨터의 값이다.
1. 최저값은 당연히 1
2. 최고값은 최저성능의 컴퓨터의 값 (1 <= v <= 1,000,000,000) + 비용으로 업그레이드 할 수 있는 값의 최대 (1e18 ** 0.5 = 1,000,000,000) = 2,000,000,000 이다.
이분탐색을 통해서 계산한다.
1. 현재 예산은 B
2. 업그레이드 할 때 드는 비용이 예산을 벗어날 경우 break를 통해 빠져나간다.
  1. 빠져나가면서 범위를 줄여준다.
  2. 현재 값이 크기 때문에 예산을 벗어난 것이므로 right 값을 줄인다.
3. 빠져나가지 못하고 전부 돈 경우
  1. 예산 안에서 해결이 된다는 의미이다.
  2. left 값을 키움으로써 범위를 줄일 수 있다.
찾은 값은 결국 (left+right) // 2 이지만 left와 right 값이 같아지면서 while 문이 종료되기 때문에 left나 right를 출력하면 끝.