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

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

17245번: 서버실

 

🖇 이진 탐색

 

코드

# 17245
# 시간초과 나는 걸로 봐선, 단순 반복문으로 풀면 안된다.
# 그럼 이진 탐색으로? L==1, R==10,000,000 을 초기값으로 탐색하는 것?
input = __import__('sys').stdin.readline
n = int(input())
li = []
for i in range(n):
    li.append(list(map(int,input().split())))
sm = 0
mx = 0
for i in range(n):
    for j in range(n):
        sm += li[i][j]
        mx = max(mx, li[i][j])
left = 0
right = mx
temp = [] # 조건에 만족하는 경우를 모두 저장해두고, 여기서 min값을 뽑으면 될 듯 !
while left <= right:
    mid = (left + right) // 2
    ans = 0
    for i in range(n):
        for j in range(n):
            if li[i][j] >= mid:
                ans += mid
            else:
                ans += li[i][j]
    if sm/2 > ans: # sm/2 <= ans을 찾는 게 목표
        left = mid + 1
    else:
        temp.append(mid)
        right = mid - 1
print(min(temp))

 

문제풀이

소요 시간의 가능 범위가 늘어져있다고 생각하고, 그 시간을 이진 탐색하여 가능한 시간 중 가장 작은 값을 출력해야 한다.

이차원 리스트에서 가장 큰 원소를 right, 0을 left로 초기값을 설정한다.

left가 right보다 커지면 탐색이 끝나게 되므로, while문의 조건을 left <= right로 설정해준다.

이제부터 이차원 리스트를 돌며 기준 시간일 때 몇 개의 컴퓨터가 작동 가능한지 카운트해주면 된다.

(이차원 리스트의 원소값이 기준 시간보다 작으면 ans 변수에 모두 더해주고, 크면 원소값을 모두 더해주는 방식으로 카운트)

그렇게해서 나온 ans 값이 전체 컴퓨터의 절반보다 크다면, mid값을 빈 리스트에 저장해주고 right를 mid의 -1 위치로 변경시킨다.

그렇지 않다면, left를 mid의 +1 위치로 이동시켜준다.

while문이 모두 끝나면, 조건을 만족하는 경우가 담긴 리스트에서 가장 작은 값을 출력해주면 끝난다.

 

 

메모

주석에도 나와있듯이, 처음엔 단순 반복문으로 접근했다. 

# 17245
input = __import__('sys').stdin.readline
n = int(input())
li = []
for i in range(n):
    li.append(list(map(int,input().split())))
sm = 0
for i in range(n):
    for j in range(n):
        sm += li[i][j]
temp = 0
ans = 0
while sm/2 > temp:
    for i in range(n):
        for j in range(n):
            if li[i][j] != 0:
                li[i][j] -= 1
                temp += 1
    ans += 1
print(ans)

시간 초과의 이유를 찾아보자면, n이 최대 1,000이므로 이중 for문은 O(n^2) = 1,000,000 이다. 추가적으로 한 칸에는 10,000,000대가 쌓여있을 수 있으므로, 이 둘을 곱한 1,000 * 10,000,000 의 시간 복잡도를 가지는게 아닌가 싶다. 근데 왜 48%까지 돌았는지는 의문이다. 훨씬 더 낮은 통과율을 보여야하는거 아닌가? 어쨌든 단순한 브루트포스로 풀 수 없다고 판단하고 이진 탐색으로 접근했다. 

또 유의할 것이, 습관적으로 /가 아닌 //을 사용하면 조건을 만족하지 않는 경우가 생긴다. 예를 들어,

sm == 101 이라면

sm//2 == 50

sm/2 == 50.5 이다.

sm과 비교하는 값을 tmp==50이라고 했을 때, 50.5 > tmp 은 만족하지만 50 > tmp은 만족하지 않는 결과가 나온다. 그러므로 / 을 사용해줘야 한다.