1450 냅색문제
-
백준 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 } 참고로 ..