Algorithm - 양팔저울(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[양팔저울(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사이의 정수 중 측정이 불가능한 물의 무게가 몇 가지인지 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 K(3 ≤ K ≤ 13)이 주어진다.

두 번째 줄에 K개의 추의 무게가 공백을 사이에 두고 주어진다.

(단, 각 추의 무게는 1부터 200,000까지임)

 

*출력 설명

첫 번째 줄에 측정이 불가능한 물의 무게 가지수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_58.txt', 'rt')

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)

if __name__ == "__main__":
    n = int(input())
    G = list(map(int, input().split()))
    s = sum(G)
    res = set()
    DFS(0, 0)
    print(s - len(res))
    
# 출력 : 2

 

input_58.txt(입력)

3
1 5 7

 

 

중요내용

1. 해당 문제의 풀이에는 상태트리와 재귀함수를 활용한 DFS 개념이 사용된다.
2. 상태트리의 노드에서 세 가지의 가지가 뻗어나간다.
3. 왼쪽 가지는 양팔저울에서 추를 왼쪽에 달고 그릇을 오른쪽에 놓는 경우이며, 가운데 가지는 양팔저울에서 추를 오른쪽에 달고 그릇을 왼쪽에 놓는 경우이다. 마지막으로 오른쪽 가지는 양팔저울의 어떤 부분에도 해당 추를 사용하지 않는 경우를 의미한다.
4. 참고로, 양팔저울의 왼쪽에 추를 사용하면 해당 무게는 (+) 부호를 가지고 반대로 오른쪽에 추를 사용하면 해당 무게는 (-) 부호를 가진다.
5.  상태트리의 각 레벨은 특정 추를 양팔저울에 사용했는지 해당 여부를 알려준다.
6. DFS() 함수의 인자 L은 상태트리의 레벨을 의미하는 동시에 리스트 G의 인덱스 번호로 사용된다. (추의 무게에 접근하는 인덱스 번호)
7. DFS() 함수의 인자 sum은 사용된 추의 총 무게 합을 의미한다.
8. 변수 res는 측정 가능한 물의 무게를 저장하는 변수이며, set 자료형으로 선언한 이유는 무게를 중복으로 고려하지 않기 위함이다.
9. DFS() 함수의 인자 sum이 음수로 나오면 해당 값은 고려하지 않는다. (상태트리의 특성 상, 해당 음수의 절대 값이 반드시 대칭적으로 등장하기 때문)
10. DFS(L+1, sum+G[L]) 코드는 인덱스 번호가 L인 추를 양팔저울의 왼쪽에 놓는 경우를 의미한다.
11. DFS(L+1, sum-G[L]) 코드는 인덱스 번호가 L인 추를 양팔저울의 오른쪽에 놓는 경우를 의미한다.
12. DFS(L+1, sum) 코드는 인덱스 번호가 L인 추를 양팔저울에 사용하지 않는 경우를 의미한다.