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

문제 링크

https://softeer.ai/practice/6252

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

정답 코드

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)

풀이 방법

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

느낀점

https://sound-programming.tistory.com/129

프로그래머스 [Lv. 4] 징검다리 {언어 : Python}

• 이 문제나 이거보다 쉬운 프로그래머스의 징검다리 건너기를 풀어보면 문제가 같다고 느껴진다.

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

• 개인적으로 징검다리 건너기가 조금 더 어려웠던 것 같다.