양팔저울(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까지이다.

 

▣ 출력설명

첫 번째 측정이 불가능한 가지수를 출력하세요.

 

▣ 입력예제

3

1 5 7

 

▣ 출력예제

2

---

내가 쓴 코드1

#첫번째 코드 -> 테스트케이스 4,5에서 time limit exceeded
import sys
#sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v, water, cur_weight):
    global result
    #이미 가능한거 찾음
    if result == 1:
        return
    if v == K:
        if cur_weight == water:
            result = 1
            return
    else:
        DFS(v+1, water, cur_weight+weights[v])
        DFS(v+1, water + weights[v], cur_weight)
        DFS(v+1, water, cur_weight)



if __name__=="__main__":
    K = int(input())
    weights = list(map(int, input().split()))
    total = sum(weights)
    cnt = 0
    for i in range(1,total+1):
        water = i
        result = 0
        DFS(0,i, 0)
        if result == 0:
            cnt += 1
    print(cnt)

 

내가 쓴 코드2

#두번째 코드
import sys

# sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline


def DFS(v, water, cur_weight):
    global result
    # 이미 가능한거 찾음
    if result == 1:
        return
    # 물 쪽이 너무 무거워서 추 다 올려도 절대 맞출 수 없을 때
    if water > cur_weight + sum(weights[v:]):
        return

    if v == K:
        if cur_weight == water:
            result = 1
            return
    else:
        DFS(v + 1, water, cur_weight + weights[v])
        DFS(v + 1, water, cur_weight)
        DFS(v + 1, water + weights[v], cur_weight)


if __name__ == "__main__":
    K = int(input())
    weights = list(map(int, input().split()))
    total = sum(weights)
    cnt = 0
    for i in range(1, total + 1):
        water = i
        result = 0
        DFS(0, i, 0)
        if result == 0:
            cnt += 1
    print(cnt)

 

내가 쓴 코드3

#세번째 코드
import sys
#sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v, cur_weight):
    if v == K:
        possible_weights.add(cur_weight)
        return
    else:
        DFS(v+1, cur_weight+weights[v])
        DFS(v+1, cur_weight)
        DFS(v+1, cur_weight-weights[v])

if __name__=="__main__":
    K = int(input())
    weights = list(map(int, input().split()))
    total = sum(weights)
    cnt = 0
    possible_weights = set()
    DFS(0,0)

    for i in range(1,total+1):
        if i not in possible_weights:
            cnt += 1
    print(cnt)

 

모범답안

#모범답안
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)


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

 

느낀점

1. 첫번째 코드에서 시간 초과가 나왔다. 
가지치기 조건을 추가해볼까,.

2. 두번째 코드에서도 같은 테스트케이스에서 시간 초과가 나왔다.
방식을 바꿔보자!

3. 세번째 방식에서는 dfs를 한 번만 호출해서 가능한 무게 조합을 모두 탐색하고,
그 이후에 반복문을 통해 갯수를 처리했다. => 성공!

4. DFS호출 횟수를 줄이고, 가능한 무게 종류를 효율적으로 (중복제거) 저장해서
활용한 방식이 시간 초과를 해결하는데에 기여!!

5. 모범답안은 가능한 무게를 1부터 시작해서 마지막에 반복문을 사용안하고
총 무게에서 가능한 무게의 수를 빼는 방법으로 간단히 해결했다. 
ㅎㅎ 이거까지 생각할 수는 없었당. 담부터 더 넓게 생각해보자

 

---

다시 풀어보기

import sys
#sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v, cur_sum):
    if v == K:
        if 0<cur_sum<=total:
            possible_weights.add(cur_sum)
        return
    else:
        DFS(v+1, cur_sum+weights[v])
        DFS(v+1, cur_sum-weights[v])
        DFS(v+1, cur_sum)

if __name__ == "__main__":
    K = int(input())
    weights = list(map(int, input().split()))
    total = sum(weights)
    possible_weights = set()
    DFS(0,0)
    print(total - len(possible_weights))