백준 문제풀이 - 17245 번

링크 -> https://www.acmicpc.net/problem/17245

1. 요약 및 풀이방법

정사각형 모양의 서버실에 서버 랙이 쌓여있습니다.
찬 공기가 밑에서부터 차오를 때, 서버실의 컴퓨터 중 절반 이상이 켜지는 시간을 구하는 문제입니다.

소요 시간을 전체 범위로 하여 이분탐색으로 해결하였습니다.
찬 공기가 바닥인 경우를 start,
모든 컴퓨터를 냉방 하는 경우를 end로 범위를 잡았습니다.
위에서 모든 컴퓨터를 냉방 하는 경우는 가장 높은 컴퓨터까지 찬 공기가 올라간 상태입니다.

그렇게 이분탐색을 진행하며, 전체 컴퓨터의 50% 이상이 될 때까지 반복해서 탐색합니다.

2. Code

from sys import stdin

input = stdin.readline

def main():
    N = int(input())
    computers = []
    for _ in range(N):
        computers += list(map(int, input().split()))

    total = sum(computers)
    ans = 0
    start = 0
    end = max(computers)
    while start <= end:
        mid = (start + end) // 2
        sums = 0
        for computer in computers:
            sums += computer if computer < mid else mid

        if sums < total / 2:
            start = mid + 1
        else:
            ans = mid
            end = mid - 1
    print(ans)

if __name__ == "__main__":
    main()

3. 학습 내용

간단하게 접근했지만 생각보다 디테일에서 곤란을 겪은 문제였습니다.

첫번째로는 전체 컴퓨터중 50%를 정확히 어떻게 표현할까 입니다.
왜냐하면 전체 컴퓨터가 홀수인 경우, // 연산자를 이용하면 오차가 생기기 때문입니다.
예를 들어 전체 컴퓨터가 9대 있을 경우, 9 // 2 = 4 입니다.
이때, 켜진 컴퓨터가 4대라면 절반이 켜졌다고 판단할 수 있기 때문입니다.
때문에 / 연산자를 이용해서 조건문을 작성하였습니다.

두번째로는 켜진 컴퓨터를 누적합 하는 과정에서,
찬공기보다 낮은 높이는 해당 서버 랙 높이를,
찬공기보다 높은 높이는 현재 공기 높이를 더하기 위해
모든 element에 min 함수를 이용해 구해주니 시간 초과가 발생했습니다.
따라서 조건문으로 변경하여 작성하였습니다.

마지막으로 코드에서 굳이 이중배열을 사용할 필요는 없기 때문에 편하게 1차원 리스트로 정리하여 작성하였습니다.

4. 결과