[백준/파이썬][Silver I] 양팔저울 - 17610

[Silver I] 양팔저울 - 17610

문제 링크

성능 요약

메모리: 206480 KB, 시간: 220 ms

분류

브루트포스 알고리즘

제출 일자

2025년 1월 21일 12:11:30

문제 설명

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

X	1	2	3	4	5	6	7	8	9
	□:1	□:2	□:(1+2)	(□+2):6	(□+1):6	□:6	□:(1+6)	□:(2+6)	□:(1+2+6)

만약 추의 무게가 {1, 5, 7}이면 S = 13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

k(3 ≤ k ≤ 13)개 추 무게 g₁, g₂, ..., g_k가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

입력

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3 ≤ k ≤ 13)가 주어진다. 다음 줄에는 k개의 정수 g_i(1 ≤ g_i ≤ 200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

출력

1부터 S(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

풀이

def find_possible_weights(weights) :
    possible_weights = set()

    def measure(idx, left_sum, right_sum) :
        # 베이스 케이스 : 모든 추를 고려했을 때
        if idx == len(weights) :
            if left_sum != 0 or right_sum != 0 :    # 최소한 하나의 추는 사용해야 함
                possible_weights.add(abs(left_sum - right_sum))
            return

        # 현재 추를 사용하지 않는 경우
        measure(idx + 1, left_sum, right_sum)

        # 현재 추를 왼쪽에 놓을 경우
        measure(idx + 1, left_sum + weights[idx], right_sum)

        # 현재 추를 오른쪽에 놓을 경우
        measure(idx + 1, left_sum, right_sum + weights[idx])

    measure(0, 0, 0)
    return possible_weights

k = int(input())
weights = list(map(int, input().split()))

possible_weights = find_possible_weights(weights)
if 0 in possible_weights :
    possible_weights.remove(0)

print(sum(weights) - len(possible_weights))

풀어놓고 보니 참 어이가 없었다. 이 부분은 클로드의 도움을 받긴 했지만, if 0 in possible_weights : 부분이 없어서 계속해서 틀렸다. 

뭐 우선 다른 코드를 봐도 비슷한 로직으로 구성되었다는 것을 알 수 있다. 한 쪽은 재귀로, 다른 한 쪽은 for loop로 구현하였다. 

다른 코드로 풀어본 결과는 

k = int(input())
weights = list(map(int, input().split()))

possible_weights = [weights[0]]

for i in range(1, k) :
    tmp = [weights[i]]

    for w in possible_weights :
        tmp += [weights[i] + w, abs(weights[i] - w)]
    possible_weights += tmp

possible_weights = set(possible_weights)

if 0 in possible_weights :
    possible_weights.remove(0)

print(sum(weights) - len(possible_weights))

함수로 구현한 코드는 확실히 오래걸리는 모습을 보여주고 for loop가 시간적으로 덜 걸리는 모습을 보여주었다. 

최근에 solved.ac 의 마라톤 도전 중이다.