Data Structures & Algorithms

[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-양팔저울(DFS)

숄구-ml 2022. 5. 28. 15:46

 

  • 일단 물 그릇과 추가 양팔 저울 상에서 균형을 유지해야 한다는 것을 생각해야 한다 
  • 그리고 물 그릇을 오른쪽에 고정한다고 가정하고 추는 왼쪽, 오른쪽, 혹은 아예 놓지 않는 3가지의 경우를 생각하여 물그릇에 물을 얼만큼 채워야 균형을 유지할지 고려하면 된다.

 

 

 

 

 

    • 여기서 이제 주의해야 할 것은 물의 무게가 마이너스가 되는 경우는 문제에서 고려하지 않고 - 따라서 물의 무게가 플러스일 때만 고려했다
    • 결과가 되는 물의 무게가 중복 될 수 있다는 것을 고려해야 한다 - 따라서 자료형 Set을 사용했다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def DFS(level, sum):
 
    if level == n:
        if sum > 0:
           res.add(sum) # 물의 무게가 마이너스인 경우는 제외
    else:
        DFS(level+1, sum+weights[level])    # 추를 왼쪽에 놓는 경우
        DFS(level+1, sum-weights[level])    # 추를 오른쪽에 놓는 경우
        DFS(level+1, sum)                   # 추를 놓지 않는 경우
 
if __name__ == '__main__':
 
    n = int(input())
    weights = list(map(int, input().split()))
    water = sum(weights)
 
    res = set()
    DFS(0, 0)
    print(water - len(res))     # 물의 무게의 개수에서 위에서 계산되서 나온 물의 무게의 개수의 차를 print 해줬다
 cs
 
    
728x90