[SWEA] D4. 준환이의 양팔저울

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

SW Expert Academy

 

 

1. 해결방법

완전 탐색 DFS로 해결해야하는 것은 금방 눈치챘다.

무게 추가 순서에 맞게 가지는 경우를 리스트로 구하고, 왼쪽과 오른쪽 무게 추를 비교해서 나온 경우의 수를 answer에 +1한다.
하지만, 최대한의 가지치기를 했음에도 21게 테스트 중에 고작 1개의 케이스에서 시간초과가 걸렸다.
순열 부분을 perm 라이브러리를 사용해야하나..? 왜지? 

해결이 안되었기에 다음에는 perm 라이브러리를 사용해서 순열을 쉽게 만들고 가지치기를 똑같이 해봐야겠다.

물론 다음에.,...

 

 

2. 시간초과 코드

for test_case in range(1, T + 1):
    N = int(input())
    numbers = list(map(int, input().split()))
    chk = [False] * N

    def recur(left, right, depth, rst):
        global total, answer, N

        if depth == N:
            answer += 1
            return

        now = rst[depth]
        if left > total // 2:
            answer += 2 ** (N - depth)
            return
        elif left >= now + right:
            recur(left, now + right, depth + 1, rst)
            recur(now + left, right, depth + 1, rst)
        else:
            recur(now + left, right, depth + 1, rst)



    def dfs(rst):
        global total, answer

        if len(rst) == N:
            recur(0, 0, 0, rst)
            return

        for j in range(N):
            if chk[j] == False:
                chk[j] = True
                rst.append(numbers[j])
                dfs(rst)
                chk[j] = False
                rst.pop()

    answer = 0
    total = sum(numbers)
    result = []
    for i in range(N):
        if chk[i] == False:
            chk[i] = True
            result.append(numbers[i])
            dfs(result)
            chk[i] = False
            result.pop()

    print(f'#{test_case} {answer}')

 

 

3. 정답 코드

python 내에서 itertools 라이브러리의 permutations 순열 기능을 사용해서 해결하였다.

확실히 완전탐색 dfs 보다는 permutations를 이용한 탐색이 조금 더 시간복잡도 면에서 안정적인 것 같다.

 

from itertools import permutations

T = int(input())
# T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    numbers = list(map(int, input().split()))
    chk = [False] * N


    def dfs(left, right, depth, p):
        global answer, total

        if depth == N:
            answer += 1
            return

        now = p[depth]
        if left > (total // 2):
            answer += 2 ** (N - depth)
            return
        elif left >= (right + now):
            dfs(left, right + now, depth + 1, p)
            dfs(left + now, right, depth + 1, p)
        else:
            dfs(left + now, right, depth + 1, p)


    answer = 0
    total = sum(numbers)
    for perm in permutations(numbers, N):
        dfs(0, 0, 0, perm)

    print(f"#{test_case} {answer}")