냅색문제 (1) 썸네일형 리스트형 [BOJ] 백준 1450 냅색문제 (Swift) 문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이 문제는 dfs + 이분탐색으로 풀이할 수 있습니다. n이 최대 30이므로, 모든 경우의 수를 고려하면 $2^30$ = 약 10억의 비용이 드므로 시간초과가 나올 것입니다. 어떻게 시간복잡도를 줄일 수 있을까요? n을 반씩 나누어서 시간복잡도를 줄일 수 있습니다. 예를 들어 [1, 2, 3, 4] 라는 무게가 주어졌다면, [1, 2]와 [3, 4]를 나누어서 가방에 넣을지 말지를 정해.. 이전 1 다음
