Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
5.동전분배하기 문제 밑에코드도 정답이될까요?
Viết
·
99
0
n = int(input())
c = []
for _ in range(n):
b = int(input())
c.append(b)
def DFS(L,first,second,third):
global best
a = max(first,second,third) - min(first,second,third)
if a >= best:
return
if L == n:
if a < best:
best = a
else:
for i in range(n):
if ch[i] == 0:
ch[i] = 1
DFS(L+1,first+c[i],second,third)
DFS(L+1,first,second+c[i],third)
DFS(L+1,first,second,third+c[i])
ch[i] = 0
ch = [0] * n
best = 10000000000000
DFS(0,0,0,0)
print(best)Câu trả lời 1
0
안녕하세요, 인프런 AI 인턴입니다.
yswo2100님께서 작성하신 DFS 코드는 동전 분배 문제에서 상태 트리를 활용하여 가능한 모든 경우의 수를 탐색하고 있습니다. 코드를 분석하면, 각 동전이 세 사람에게 분배될 때 최대 금액과 최소 금액의 차이를 최소화하도록 하는 목표가 있는 것으로 보입니다.
몇 가지 주의해야 할 점과 개선 방안을 말씀드리겠습니다:
비교 조건:
DFS함수 안에서a >= best조건으로 바로return을 하고 있습니다. 이 조건은 탐색 중인 현재 상태에서 이미 최악의 경우보다 나쁜 경우라면 더 이상 탐색할 필요가 없다는 의미입니다. 이 조건은 올바른 가지치기 방법이지만, 다른 상태들에서 더 나은 경우가 존재할 가능성을 놓칠 수 있으므로 코드의 의미를 잘 이해하고 사용해야 합니다.중복 DFS 호출: 현재 코드는 모든 동전을 여러 번 추가할 수 있는 구조를 가지고 있습니다. 중복되는 상태도 포함될 수 있으므로 이러한 구조가 올바른지 확인해야 합니다.
동전 선택 변수: 코드에서
ch배열을 활용하여 이미 사용된 동전을 추적하고 있습니다. 이는 중복을 피하는 데 유용하지만, 현재 코드에서는 각 동전을 세 사람에게 세 번 추가하는 방식으로 보입니다. 이러한 선택 방법이 논리적으로 맞는지 체크해 보아야 합니다.
추천 자료
이전에 유사한 질문들이 있어 참조하시는 것도 도움이 될 수 있습니다:
- “이렇게 해도 괜찮은건가요?”: 이 질문에서는 DFS를 사용한 다른 방식의 접근과 효율성에 대해 논의하고 있습니다.
- “시간 초과”: DFS를 구현하면서 시간 초과에 대한 해결책을 찾는 방법에 대한 토론입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.