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

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편)

 

 

 

📖 문제 : 양팔 저울

무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0 으로 간주한다.
양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다.
주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이 면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다.

만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다.
K(3<=K<=13)개의 추 무게가 주어지면, 1부터 S사이의 정수 중 측정이 불가능한 물의 무게는 몇 가지가 있는 지 출력하는 프로그램을 작성하세요.

 

import sys
input = sys.stdin.readline

def DFS(L, sum):
  global res
  if L==n:
    if 0<sum<=s:
      res.add(sum)
  else:
    DFS(L+1, sum+G[L])
    DFS(L+1, sum-G[L])
    DFS(L+1, sum)

n = int(input())
G = list(map(int, input().split()))
s = sum(G)
res = set()
DFS(0, 0)
print(s-len(res))

 

 

⭐️ Point ! ⭐️

• +,-값으로 측정하는 물의 값을 왼쪽, 오른쪽으로 구분.

 

•  python에서의 set()함수 ! 
  : set()은 집합 관련한 것을 쉽게 처리하기 위해 사용.
   특징 
  : 중복 허용 X, 순서 없음
  set 자료형에 데이터를 추가하려면 add함수를 사용해야함 
  
  
• 결국 여기서 set함수를 사용한 이유는 중복값을 처리하기 위해서 사용

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이

참고

https://velog.io/@insutance/Python-set-%EC%9D%B4%EB%9E%80 

[Python] set() 이란