[백준][파이썬] 17245번. 서버실

문제

https://www.acmicpc.net/problem/17245

 

풀이

첫 번째 시도

아무생각없이 짠 코드이다.

시간을 하나씩 증가시켜가며, NxN의 모든 칸을 돌면서 제대로 동작하는 컴퓨터가 전체 컴퓨터의 절반을 넘었는지를 체크하는 방식으로 했고, 당연하게도 시간초과가 떴다.

N = int(input())
comp = []
total = 0
for _ in range(N) :
  temp = list(map(int, input().split()))
  comp.append(temp)
  total += sum(temp)

time = 0  # 시간
temp = 0  # 동작하는 컴퓨터 개수

while (temp * 2 < total) :
  time += 1
  for i in range(N) :
    for j in range(N) :
      if comp[i][j] >= 1 :
        comp[i][j] -= 1
        temp += 1
print(time)

그런데 생각해보니, 이 문제에서 컴퓨터들의 위치는 필요없는 정보였다.

NxN 형태를 유지하며 풀지 않아도 되고, 컴퓨터들의 입력 순서도 무시해도 된다는 뜻이다.

그래서 컴퓨터의 개수들을 그냥 리스트로 받아서 이분탐색을 통해 문제를 풀어보기로 했다.

 

두 번째 시도 (성공)

N = int(input())
comp = []
for _ in range(N) :
  comp.extend(list(map(int, input().split())))

total = sum(comp)
comp.sort()

answer = []  # 정답 후보 시간들 저장
target = total / 2
start, end = 0, comp[-1]  # 쌓여 있는 컴퓨터의 최소 개수와 최대 개수

while (start <= end) :
  mid = (start + end) // 2
  temp = 0  # 동작하는 컴퓨터의 수
  for i in range(N**2) :
    if comp[i] >= mid :
      temp += mid
    else :
      temp += comp[i]

  if temp < target :
    start = mid + 1
  else :
    end = mid - 1
    answer.append(mid)
print(min(answer))