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

Question

제가 코드를 짰는데 99퍼에서 오답처리가 났는데 어느부분을 놓쳤는지 모르겠어서 질문 드립니다. 코드 한 번 봐주실 수 있을까요.. def func(idx,p,f,s,v,sum1): global min_sum if sum1 > min_sum: return if idx == N: 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 elif sum1 == min_sum: return else: 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=' ')

박성인 · Answer

답변 감사합니다!! 아직 이해 안되는 부분이 있어 댓글 답니다! 제가 강의를 보면서 이해한건 idx == N 까지 확인하는 경우면 결국 첫번째부터 마지막 요소까지 o,x로 그려나가면서 모든 부분집합을 훑는다고 이해했는데 이 부분에서 탐색하지 못한 반례가 있을 수 있는건가요?

코딩 센세 · Answer

조금 수정해봤습니다.   보내주신 코드와 결정적으로 다른점은 보내주신 코드 [ 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=' ')