[Algorithm] BOJ 17245

BOJ 17245번 서버실

Intro

처음에는 Python으로 풀었는데 80%대에서 시간 초과가 계속해서 났습니다.
더 이상 시간을 줄일 수 있는 곳이 보이질 않아서 동일한 코드를 Swift로 바꿔 풀었더니 시간 초과가 해결되었습니다.

Solution

1. 입력을 받으면서 가장 높은 높이와, 컴퓨터 개수의 총 합을 구합니다.
2. 컴퓨터 개수의 총 합의 절반을 target으로 설정합니다.
3. 이분 탐색을 통해 target 이상의 컴퓨터가 켜지는 최소 높이를 찾습니다.

Code

Swift

import Foundation

func count(_ mid: Int, _ coms: [[Int]]) -> Double {
    var count = 0
    for com in coms {
        for c in com {
            count += min(c, mid)
        }
    }
    return Double(count)
}

let n = Int(readLine()!)!
var coms = Array<[Int]>()
var l = 0
var r = 0
var target: Double = 0
for _ in 0..<n {
    let com = readLine()!.split(separator: " ").map(){Int($0)!}
    coms.append(com)
    r = max(r, com.max()!)
    target += Double(com.reduce(0, +))
}
target /= 2
var result = 0
while l <= r {
    let mid = (l+r)/2
    if count(mid, coms) >= target {
        result = mid
        r = mid-1
    } else {
        l = mid+1
    }
}
print(result)

Python

# **통과되는 코드가 아닙니다.**
# 시간 초과 걸리는 코드입니다. 참고용으로 첨부합니다.
import sys
input = sys.stdin.readline

def count(mid) :
    count = 0
    for com in coms : 
        for c in com :
            count += min(c, mid)
    return count

n = int(input().strip())
coms = []
target = 0
l = 0; r = 0
for _ in range(n) :
    com = list(map(int, input().strip().split()))
    coms.append(com)
    target += sum(com)
    r = max(r, max(com))
target /= 2
result = 0
while l <= r :
    mid = (l+r)//2
    if count(mid) >= target :
        result = mid
        r = mid-1
    else : l = mid+1
print(result)