인프런 커뮤니티 질문&답변
작성한 질문수
5강 최적화 19942번 질문드립니다.
해결된 질문
작성
·
287
·
수정됨
1
제가 코드를 짰는데 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=' ')
답변 2
1
코딩 센세
지식공유자
조금 수정해봤습니다.
보내주신 코드와 결정적으로 다른점은
보내주신 코드
[ 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=' ')
아래 반례를 확인해보시면 됩니다!
제가 쓴 코드는, idx가 끝에 도달하지 않아도 정답 조건을 만족하면 정답을 업데이트 하고 종료되지만,
성인님이 쓴 코드는 반드시 마지막 idx에 도달하도록 조건이 걸려 있기 때문에,
영양소가 없는 재료 ( 좀 억지 반례이긴 하지만 ) 가 있다는 가정 하에 아래와 같이 다른 결과가 나오게 됩니다!
[반례]
3
0 0 0 1
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
[성인님이 쓴 코드 결과]
1
1 2 3
dict1 = {1: '0111'}
[제가 쓴 코드 결과]
1
1
dict1 = {1: '0100'}
이런 반례는 사실 저도, 처음부터 이런 반례가 있겠군! 하고 생각하고 푸는 건 아니고
조건문의 사용이나 가지치기의 위치, 등을 조금 반례가 생기지 않도록 문제를 계속 풀어보고 조정해 나가면서 자연스럽게 알게 되는 스킬이라서 정말로 좋은 질문이었습니다!
반례가 조금 억지네요.. 어이없다