[백준 | 실버4] Bookshelf 2(백트랙킹, 부분수열의 합)

문제

농부 John은 최근에 젖소 도서관을 위해 또 다른 책장을 샀는데, 선반이 꽤 빨리 채워지고 있으며 이제 사용할 수 있는 유일한 공간은 맨 위입니다.

FJ에는 H_i(1 <= H_i <= 1,000,000 - 이들은 매우 키가 큰 젖소)의 키를 가진 N개의 젖소(1 <= N <= 20)가 있습니다. 책장의 높이는 B입니다(1 <= B <= S, 여기서 S는 모든 젖소 높이의 합).

책장 꼭대기에 도달하기 위해 한 마리 이상의 젖소를 쌓아 올려서 총 높이가 개별 높이의 합이 되도록 할 수 있습니다. 이 총 높이는 소가 꼭대기에 닿을 수 있도록 책장의 높이 이상이어야 합니다.

필요한 것보다 더 높은 소 더미는 위험할 수 있으므로 귀하의 임무는 더미가 책장에 닿을 수 있도록 가능한 한 가장 작은 높이의 소 더미를 생산하는 소 세트를 찾는 것입니다. 프로그램은 최적의 소 더미와 책장 사이의 최소 '초과' 높이를 인쇄해야 합니다.

입력

• 1행: 두 개의 공백으로 구분된 정수: N 및 B
• 라인 2..N+1: 라인 i+1은 단일 정수를 포함합니다: H_i

 

출력

• 1행: 최적의 젖소 세트의 총 높이와 선반 높이 간의 (음수가 아닌) 차이를 나타내는 단일 정수.

 

예제 입력 1 복사

5 16
3
1
3
5
6

예제 출력 1 복사

1

힌트

여기서 우리는 3 + 3 + 5 + 6 = 17의 총 높이에 대해 젖소 1, 3, 4 및 5를 사용합니다. 총 높이 16을 얻을 수 없으므로 답은 1입니다.

 

문제풀이

한 마리 이상의 젖소를 쌓아 올려서 총 높이가 꼭대기에 닿을 수 있도록 책장의 높이 이상 만들기

가능한 한 가장 작은 높이의 소 더미를 생산하는 소 세트 생성
최적의 소 높이의 합 - 책장 높이 출력

문제해결

일반적인 부분수열의 합 만들기 문제
부분수열의 합을 이용해서 targetHight를 초과하는 최소 합값을 찾고 
책장높이 - 최소한의 높이의 합 출력

n, targer_num = map(int, input().split())
num_list = []
for i in range(n) :
    num_list.append(int(input()))

min = 2147000000

def DFS(L, sum) :
    global min

    if sum >= targer_num  :     #합이 목표치와 크거나 같은 경우 최소값 비교
        if min > sum :
            min = sum
            #print(min)
            return
    if L == n :                 #숫자 리스트 개수만큼 다 돌면 종료
        return

    else :
        DFS(L+1, sum+num_list[L])
        DFS(L+1, sum)

DFS(0, 0)
print(min-targer_num)