[백준 | 실버3] 6211번: The Eating Puzzle(백트랙킹, 부분수열)

https://www.acmicpc.net/problem/6211

문제

6211번: The Eating Puzzle

Bessie는 하루에 C(10 <= C <= 35,000) 칼로리 이하로 섭취할 수 있는 다이어트를 하고 있습니다. 농부 John은 B(1 <= B <= 21) 양동이의 사료로 그녀를 놀리고 있습니다. 각 양동이에는 약간의 (잠재적으로 고유하지 않은) 칼로리(범위: 1..35,000)가 들어 있습니다. Bessie는 자제력이 없습니다. 일단 사료 양동이에서 시작하면 모든 것을 소비합니다.

Bessie는 조합론을 그리 좋지 않습니다. 한계 C를 초과하지 않고 베시에게 많은 칼로리를 제공하는 최적의 사료 버킷 조합을 결정합니다.

예를 들어, 40칼로리와 7, 13, 17, 19, 29, 31칼로리의 6개 버킷이 있다고 가정해 보겠습니다. Bessie는 7 + 31 = 38칼로리를 먹을 수 있지만 7 + 13 + 19 = 39칼로리의 세 양동이를 섭취하면 더 많이 먹을 수 있습니다. 그녀는 더 나은 조합을 찾을 수 없습니다.

입력

• 1행: 공백으로 구분된 두 정수: C 및 B
• 2행: 버킷 1, 2 등의 칼로리 수를 각각 지정하는 공백으로 구분된 B 정수

 

출력

• 1행: Bessie가 섭취하고도 여전히 식단을 유지할 수 있는 최대 칼로리 수인 단일 정수가 있는 단일 행.

예제 입력 1 복사

40 6
7 13 17 19 29 31

예제 출력 1 복사

39

 

문제풀이

부분 수열 문제

부분 수열로 만들 수 있는 합을 구하는데

B개 중의 숫자에서 만들 수 있는 숫자인데 C보다 작은데 값을 찾아라

 

문제해결

사용한다 / 사용하지 않는다 문제

DFS(L+1, num_list[L]를 사용한다)

DFS(L+1, num_list[L]를 사용하지 않는다)

 

종료 조건은 만들수 있는 부분수열의 개수(n)과 같을때 return

n보다 작을때는 조건에 맞게 cal보다 작을때 그리고 max보다는 크게를 찾아준다.

cal, n = map(int, input().split())
num_list = list(map(int, input().split()))
max = -1

def DFS(L, sum) :
    global max
    
    if L < n + 1:
        if sum < cal and max < sum :
            max = sum
    if L == n :
        return

    else :
        DFS(L+1, sum+num_list[L])       #사용한다
        DFS(L+1, sum)                   #사용하지 않는다

DFS(0, 0)
print(max)