[김태원 알고리즘] 양팔저울 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(idx, pSum):
    if idx == K:
        if 0 < pSum <= S and visited[pSum] != 1:
            visited[pSum] = 1
    else:
        DFS(idx + 1, pSum) # 사용 X
        DFS(idx + 1, pSum + lst[idx]) # 더하거나
        DFS(idx + 1, pSum - lst[idx]) # 빼거나

K = int(input())
lst = list(map(int, input().split()))

S = sum(lst)
visited = [0] * (S+1)

DFS(0, 0)
print(visited.count(0) - 1) # ✅ 0번 인덱스 제외

• 정답!
• 각각의 추를 사용하거나(더하거나 빼거나), 사용하지 않거나 -> 총 3가지 경우로 나눠서 DFS를 돌리면 된다.
  • 뺀다는 것은 물 그릇과 같은 쪽에 추를 놓는 경우이다.

다른 풀이 - set 자료구조 활용

def DFS(idx, pSum):
    if idx == K:
        if 0 < pSum <= S:
            res.add(pSum) # ✅ set에 add
    else:
        DFS(idx + 1, pSum) # 사용 X
        DFS(idx + 1, pSum + lst[idx]) # 더하거나
        DFS(idx + 1, pSum - lst[idx]) # 빼거나

K = int(input())
lst = list(map(int, input().split()))

S = sum(lst)
res = set() # ✅ set 자료구조

DFS(0, 0)
print(S - len(res))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기