부분합
-
백준 1450 냅색문제Algorithm/BOJ 2021. 4. 6. 14:48
출처: www.acmicpc.net/problem/1450 분류: 이분탐색 접근방식 n이 30으로 크기 때문에 그대로 부분합을 구하면 2^30 시간제한을 통과하기 어렵습니다. 따라서 반반 나눈 뒤 이분탐색으로 접근하는 방법으로 접근합니다. 부분합은 재귀적으로 구해줬습니다. func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) { guard sum Int { var low = 0 var high = sumB.count while low < high { let mid = (low + high)/2 if target < sumB[mid] { high = mid } else { low = mid+1 } } return low } 참고로 ..
-
백준 1806 부분합Algorithm/BOJ 2021. 1. 22. 11:43
출처: https://www.acmicpc.net/problem/1806 분류: 투포인터 접근방식 앞선 투포인터 문제와 거의 비슷했습니다. 이 문제도 전형적인 투포인터 방식으로 풀었습니다 :) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleValue() -> Int { return Int(readLine()!)! } func readArray(with separator: Character..