작은 갤러리의 큐레이터가 되어 이번 기획전에 걸 작품을 고릅니다.
후보 작품은 n개이고, i번 작품은 관람 가치 values[i]와 벽면 점유 폭 spaces[i]를 가집니다.
전시장의 벽면 폭은 총 capacity이며, 선정한 작품들의 점유 폭 합이 capacity를 넘으면 안 됩니다.
또한 작가들 사이의 사정으로 같은 전시에 함께 걸 수 없는 작품 쌍 이 존재합니다.
conflicts의 각 원소 [a, b]는 a번 작품과 b번 작품을 동시에 선정할 수 없다는 뜻입니다.
(같은 쌍이 중복해서 주어질 수 있고, 한 작품이 여러 쌍에 등장할 수 있습니다.)
두 제약을 모두 만족하도록 작품을 골랐을 때 얻을 수 있는 관람 가치 합의 최댓값 을 반환하는
solution(values, spaces, capacity, conflicts) 함수를 완성하세요.
아무 작품도 걸지 않는 것도 허용되며, 그때의 가치 합은 0입니다.
values=[10, 7, 5], spaces=[3, 2, 2], capacity=4, conflicts=[[0, 1]] → 12
0번(가치 10)은 혼자 걸면 10.
0번과 2번을 함께 걸면 폭이 3+2=5로 벽면을 초과하고,
0번과 1번은 함께 걸 수 없으므로 1번+2번(폭 4, 가치 12)이 최선이다.
values=[6, 6, 6], spaces=[2, 2, 2], capacity=6, conflicts=[[0,1], [1,2], [0,2]] → 6
폭은 세 작품 모두 걸 수 있지만 세 쌍이 모두 충돌하므로 한 점만 걸 수 있다.
values=[13, 9, 8, 5], spaces=[5, 4, 3, 2], capacity=8, conflicts=[] → 21
충돌이 없으므로 폭 8 안에서 0번+2번(폭 8, 가치 21)을 고른다.[a, b] (0 ≤ a, b < n, a ≠ b)시간 복잡도 목표: 최악 2^n 조합 탐색이지만, 남은 작품의 가치 상한과 남은 벽면 폭으로 가지를 잘라내 실전 탐색량을 크게 줄이는 것이 목표입니다.
▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.