3234. 준환이의 양팔저울[python]

dfs를 이용해서 이진탐색을 구현했더라도 시간초과 때문에 특정 조건을 마주치면 return을 해줘야 한다.

 

✔ 고려해준 사항 

1. dfs를 이용한 이진탐색 visited 리스트를 이용해서 이미 올려놓은 추는 다시 올려 놓지 않게 만들었다.

2. '왼쪽에 올려놓은 추의 합 * 2'가 '전체 추의 합' 보다 크다면 그 이후 탐색은 할 필요없이 2^k * k!(단, k는 남은 추의 개수)을 결과값에 더해주면 된다.

3. 반대로 오른쪽에 올려놓은 추의 합*2 가 전체 추의 합보다 크다면 그 이후 탐색은 할 필요없다. 

4. 조건대로 왼쪽에 올려놓은 추의 합보다 오른 쪽에 올려놓은 추의 합이 커지면 그 이후 탐색은 할 필요없다. 

5. 2의 n제곱, n 팩토리얼 값을 미리 계산해서 사용한다.

 

1~4번까지 적용해도 20/21개만 성공하고 시간초과가 떴다. 5번을 적용해주시 시간초과가 뜨지 않았다.

생각보다 math.factorial() 함수의 cost가 큰가 보다.

 

👍 배운점

1. 0팩토리얼은 1이다. 수학적으로도 0팩토리얼은 1이라고 한다.

꼭 수학적으로 생각하지 않더라도 

이 문제에서 2^k * k!를 계산할 때 k가 0인 경우를 계산하는 상황이 발생하는데 k의 0팩토리얼을 0이라고 생각해서 계속 이상한 값이 나왔다. k가 0인 경우는 _depth가 마지막까지 도달했을 때 if((_lsum)*2 > isum): 조건을 만족하면서 발생한다. 이 때 res에 +1을 해줘야 하기 때문에 0팩토리얼을 1로 해줘야 한다. 

 

 

2. 주어지는 데이터 값이 적다면 미리 값을 계산 하는 것이 시간초과를 해결할 수 있는 열쇠이다.

이 문제에서는 2의 n제곱과 n팩토리얼을 미리 계산하는 것이 시간초과를 해결하는데 도움이 되었다.

 

내 코드

def dfs(_depth, _lsum, _rsum):
    global n
    global visited
    global res
    global ilist
    global isum
    global __2n
    global __nFac



    if(_lsum < _rsum):
        return

    if((_lsum)*2 > isum):
        res += __2n[n-_depth] * __nFac[n-_depth]
        return

    if((_rsum)*2 > isum):
        return


    if(_depth == n):
        res += 1
        return


    for i in range(n):
        if(visited[i] == 0):
            visited[i] = 1
            dfs(_depth+1, _lsum+ilist[i], _rsum)
            dfs(_depth+1, _lsum, _rsum+ilist[i])
            visited[i] = 0

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())

    __2n = [1,2,4,8,16,32,64,128,256]
    __nFac = [1,1,2,6,24, 120, 720, 5040, 40320, 362880]

    ilist = list(map(int, input().split()))
    isum = sum(ilist)
    res = 0

    visited = [0]*n
    
    for i in range(n):
        visited[i] = 1
        dfs(1, ilist[i], 0)
        visited[i] = 0

    print('#'+str(test_case)+' '+ str(res))