5강 최적화 19942번 질문드립니다.

답변 감사합니다!!

아직 이해 안되는 부분이 있어 댓글 답니다!

제가 강의를 보면서 이해한건

idx == N 까지 확인하는 경우면 결국 첫번째부터 마지막 요소까지 o,x로 그려나가면서

모든 부분집합을 훑는다고 이해했는데 이 부분에서 탐색하지 못한 반례가 있을 수 있는건가요?

조금 수정해봤습니다.

보내주신 코드와 결정적으로 다른점은

보내주신 코드

[ idx ==N일 때만, 영양소 조건을 확인해서 정답을 업데이트]

수정 한 코드

[ idx ==N이 아니더라도, 영양소 조건을 확인해서 정답을 업데이트]

해당 부분에 반례가 존재해서 99%에서 오류가 발생하는 것 같아요!

혹시라도 이해가 안되신다면 답글 남겨주세요!

def func(idx,p,f,s,v,sum1):
    global min_sum

    # 가지치기
    if sum1 > min_sum:
        return
    
    # 정답 업데이트    
    if p >= mp and f >= mf and s >= ms and v >= mv:
        if sum1 < min_sum:
            min_sum = sum1
            last1 = ''.join(map(str, visited))
            dict1[min_sum] = last1
            return
        
    # 인덱스 끝에 도달하면 탐색 종료    
    if idx == N:
        return
    
    # 탐색
    else:
        visited[idx+1] = 1
        func(idx+1,p+info[idx][0],f+info[idx][1],s+info[idx][2],v+info[idx][3],sum1+info[idx][4])
        visited[idx+1] = 0
        func(idx+1,p,f,s,v,sum1)


N = int(input())
mp, mf, ms, mv = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(N)]
min_sum = 999999999999999999
visited = [0] * (N+1)
dict1 = {}
func(0,0,0,0,0,0)

if min_sum == 999999999999999999:
    print(-1)
else:
    print(min_sum)
    for i in range(1,N+1):
        if dict1[min_sum][i] == '1':
            print(i, end=' ')