[Python-CodingTest] 7-3. 양팔저울 (DFS)

양팔저울

문제 정리

입력

3 // 추의 개수
1 5 7 // 각각의 추의 무게

처리 과정

1. 추를 양팔저울 왼쪽에 놓는 경우, 오른쪽에 놓는 경우, 사용하지 않는 경우로 나눈다.
2. 왼쪽에 놓으면 추의 무게(weight[L])를 더한다.
3. 오른쪽에 놓으면 추의 무게(weight[L])를 뺀다.
4. 사용하지 않으면 무게는 그대로이다.
5. 만약 음수가 나온다면 물이 오른쪽에 위치한게 아니라 왼쪽에 위치한 것이고, 반드시 대칭이 나오므로 무시한다.

출력

2

풀이

import sys
sys.stdin = open("./input/in3.txt", "rt")

def DFS(L,sum): # L은 각각의 추들 [1,5,7] # sum은 측정할 수 있는 물의 무게
    global res
    if L==n:
        if 0<sum<=s: # sum이 양수일 때 (음수이면 대칭이 나올거니까 무시)
            res.add(sum)
    else:
        DFS(L+1,sum+weight[L]) # 추를 저울의 왼쪽에 놓는 경우
        DFS(L+1,sum-weight[L]) # 추를 저울의 오른쪽에 놓는 경우
        DFS(L+1, sum) # 추를 사용하지 않는 경우

if __name__=="__main__":
    n=int(input())
    weight=list(map(int,input().split())) # 추 리스트

    s = sum(weight) # 추 무게의 총 합
    res=set() # 측정될 수 있는 물의 무게 - 중복을 제거하기 위해 set 사용
    DFS(0,0)
    
    print(s - len(res)) # set 자료구조의 길이는 len() 이용

정리

• 중복을 제거하고 싶다면 set() 자료구조 사용
• set 자료구조의 길이는 len() 이용
• set 원소의 총 합은 sum() 이용

---

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

맨 위로 이동하기