[코테] 경우의 수 고려하기 - Recursion, Backtracking

여러 가지 경우의 수를 파악해서 최선의 조건을 선택해야하는 문제

예를 들면, knapsack 문제.

물건의 수와 배낭의 최대 한도 무게가 주어졌을 때, 배낭에 가장 가치 있게 많은 물건을 담을 수 있는 경우의 수를 선택하고 그떄의 가방의 무게를 구하는 경우

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 6)

def recur(idx, weight, value):
    global max_value

    if weight > b:
        return 

    if idx == a:
        max_value = max(value, max_value)
        return

    # 물건을 선택하는 경우
    recur(idx+1, weight+items[idx][0], value+items[idx][1])
    # 물건을 선택하지 않는 경우
    recur(idx+1, weight, value)

a, b = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(a)]

max_value = int(-1e9)

recur(0, 0, 0)

print(max_value)

재귀함수 세팅

1. Parameter: 계속해서 tracking 해줄 필요 (값이 갱신되는 변수들)가 있는 변수를 parameter로 설정해준다.

2. Condition: 재귀함수를 끝낼 조건을 세팅해준다. 예를 들면 tracking 중이 index가 out of list가 될 때 / 문제에 다른 조건이 부여되었을 때

3. Function Call: 해당 옵션을 선택할지 하지 않을지에 대한 case로 나누어서 재귀함수를 호출해준다. 이때 argument를 적절히 선택해서 다음 동작과 연결되게끔 해준다.

주의 사항

1. 파이썬에서는 재귀함수 limit이 1000번이기 때문에 따로 boundary를 설정해줘야함

   sys.setrecursionlimit(10 ** 6)

2. 어떤 선택지를 선택했는지 tracking하고 싶다면 array를 따로 설정해주고 해당 옵션을 선택하는 재귀함수 호출 전에 append(), 호출 후에 pop()을 해준다.

# 영양성분 경우의 수 선택 문제 - 재귀

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 6)

def recur(idx, A, B, C, D, price):
    global answer
    global answer_used
    global used

    if idx == n:
        return

    if A >= _A and B >= _B and C >= _C and D >= _D: # 모든 영양소 충족
        if answer > price: # 가격이 덜 나갈 때만 값 갱신
            answer = price
            answer_used = list(used)

    # 재료를 사용한 경우
    used.append(idx+1)
    recur(idx+1, A+ingre[idx][0], B+ingre[idx][1], C+ingre[idx][2], D+ingre[idx][3], price+ingre[idx][4])
    used.pop()

    # 재료를 사용하지 않은 경우
    recur(idx+1, A, B, C, D, price)

n = int(input())
_A, _B, _C, _D = map(int, input().split())
ingre = [list(map(int, input().split())) for _ in range(n)]
used = []
answer_used = []

answer = int(1e9)

recur(0, 0, 0, 0, 0, 0)


if answer_used:
    print(answer)
    print(*sorted(answer_used))
else:
    print(-1)