알고리즘 스터디 - 백준 17245번 : 서버실

문제 해석

목적 : 서버실의 컴퓨터 중 절반 이상이 켜지려면 필요한 시간

1. 서버실의 크기를 위한 N 제공
2. 각 칸에 최대 천만대가 쌓임

어떤 알고리즘을 사용해야할까?

컴퓨터의 합이 증가하는 방식을 살펴보면

[1, 2, 3, 4, 5]가 있을 때

• 레벨이 1이면 : 1보다 큰 모든 요소의 개수마다 1을 더함
• 레벨이 2이면 : 2보다 큰 모든 요소의 개수마다 2를 더하고 기존에 작은 요소까지 더함

이런 식으로 움직이는 것을 알 수 있다. 컴퓨터의 최대 크기가 천만개이므로 0부터 시작하는 것은 매우 힘들다 중간을 넘어가는 최적의 값을 구하기 위해서 이진 탐색 알고리즘을 이용해 적절한 높이를 선정하는 것이 좋을 것이다.

알고리즘 코드

python3은 시간초과가 나오고 pypy3는 맞았는데 이렇게 지나가도 되는건지는 의문이다.

# 서버실 크기
N = int(input())

# 각 칸의 컴퓨터
computer = []
total_computers = 0
max_value = 0

# 입력받기
for _ in range(N):
    number = list(map(int, input().split()))
    computer.append(number)
    max_value = max(max_value, max(number))
    total_computers += sum(number)

# 냉동의 높이
level = 0

# 이진 탐색 시작
first, last = 0, max_value
while first <= last:
    mid = (first + last) // 2
    total_value = 0
    for i in range(N):
        for j in range(N):
            total_value += (mid if mid <= computer[i][j] else computer[i][j])
    
    if total_value >= total_computers/2:
        level = mid
        last = mid - 1
    else:
        first = mid + 1

print(level)