[SWEA] #3234 준환이의 양팔저울

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE&problemTitle=3234

풀이 방법

1. 주어진 숫자들에 대해 모든 순열을 구한다.
2. 각 순열에 대해서 숫자를 하나씩 왼쪽, 오른쪽에 올리면서 dfs

이 방법을 생각해내고 아래 시간 줄인 방법 1, 2 까지는 했는데 더 시간을 줄이는 방법이 생각나지 않았다. 그래서 다른 분들 코드를 몇 개 봤는데, 왼쪽에 올린 추 무게의 합이 모든 추 무게의 합의 절반을 넘으면 추가할 경우의 수를 계산하고 result에 더하는 코드를 보고 아이디어를 얻었다. 이 경우 남은 추에 대해 왼쪽에 올리거나 오른쪽에 올릴 수 있으므로 총 2가지 경우 ** 남은 추의 개수를 결과에 더해주고 리턴하면 된다.

시간 줄인 방법

1. left, right을 리스트가 아니라 정수로 관리 => tc 18
2. 순열을 perms에 전부 모으고 하나씩 put 함수 실행하지 않고, 하나가 완성됐을 경우 바로 put 함수 호출 => tc 20
3. put 함수에서 left > sum_w // 2 가지치기 조건 추가 => pass

코드

facto = [0, 1]
for i in range(2, 10):
    facto.append(facto[i - 1] * i)


def put(idx, left, right, p):
    global N, result, sum_w

    if idx == N:            # left, right 에 다 나눠담았을 경우
        result += 1
        return
    if left > sum_w // 2:   # left 가 모든 추 무게의 합 절반을 넘었으면 나머지는 안 봐도 됨 => 남은 숫자들을 left/right 에 넣는 경우의 수 더함
        n = N - idx
        result += (2 ** n)
        return

    # left 에 추를 올릴 경우
    put(idx + 1, left + p[idx], right, p)
    # right 에 추를 올릴 경우
    if right + p[idx] <= left:
        put(idx + 1, left, right + p[idx], p)


def perm(length, now, remaining):
    # 순열이 완성될 때마다 put 함수 호출
    if length == N:
        put(0, 0, 0, now)
        return

    for i in range(len(remaining)):
        perm(length + 1, now + [remaining[i]], remaining[:i] + remaining[i + 1:])


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    weights = list(map(int, input().split()))
    sum_w = sum(weights)
    result = 0
    perm(0, [], weights)

    print('#{} {}'.format(tc, result))