[Softeer] HSAT 4회 정기 코딩 인증평가 기출 | 슈퍼컴퓨터 클러스터

문제링크

---

HSAT 4회 정기 코딩 인증평가 기출 | 슈퍼컴퓨터 클러스터

풀이과정

---

범위가 굉장하다고 문제에서 경고를 줬으니, 무조건 시간초과를 만난다는 말로 들렸다 ...

그래서 생각한건 이진 탐색(Binary Search)였다.
이때 B의 범위를 봐야하는데,, 최대가 N=1이고 a1 = 10^9일때이다. 무슨 말이냐면 $2 * 10^9$ 에서 $10^9$를 빼면 $10^9$이고 이를 제곱하면 $10^{18}$이므로 최대가 된다. 그래서 성능은 2 * 10 ** 9까지 올릴 수 있다는 의미 !

아무튼 그래서 범위를 정하고 이진탐색을 했는데 어디선가 무한루프를 돌고있는 .. 내 코드 ...

미래인재TV Softeer 슈퍼 컴퓨터 클러스터 해설 동영상을 듣고 바로 해결했다.
이 영상의 11:37초부터 보면 이해가 될것이다,, 기억이 안난다면 다시 보고오기

코드

---

import sys
sys.setrecursionlimit(10**8)

def check_cost(mid):
    cost = 0
    for com in coms:
        if mid > com:
            cost += (mid - com) ** 2

    if cost <= B:
        return True
    else:
        return False

def binary_search(left, right):
    if left == right:
        return left
        
    mid = (left + right + 1) // 2
    
    if check_cost(mid):
        return binary_search(mid, right)
    else:
        return binary_search(left, mid-1)


N, B = map(int, sys.stdin.readline().split())
coms = list(map(int, sys.stdin.readline().split()))
coms.sort()
result = binary_search(coms[0], 2 * 10 ** 9)
print(result)

결과

---