Intro
처음에는 Python으로 풀었는데 80%대에서 시간 초과가 계속해서 났습니다.
더 이상 시간을 줄일 수 있는 곳이 보이질 않아서 동일한 코드를 Swift로 바꿔 풀었더니 시간 초과가 해결되었습니다.
Solution
- 입력을 받으면서 가장 높은 높이와, 컴퓨터 개수의 총 합을 구합니다.
- 컴퓨터 개수의 총 합의 절반을 target으로 설정합니다.
- 이분 탐색을 통해 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)
* 개인 블로그에 작성한 내용을 복사해왔습니다.
'Koala - 5기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
BOJ 5549(python) : 행성 탐사 (0) | 2022.02.06 |
---|---|
[백준/C++] 알고리즘 17179번 케이크 자르기 (0) | 2022.02.06 |
[BOJ / C++] 17951 : 흩날리는 시험지 속에서 내 평점이 느껴진거야 (1) | 2022.02.05 |
[BOJ / Python] 5549번: 행성 탐사 (1) | 2022.02.05 |
[백준/C++] 16713번: Generic Queries (2) | 2022.02.05 |