[Python/BOJ] 백준2629 양팔저울_DP

 

 

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

 

 

코드는 맞는 것같은데 시간초과가 난다....😥

시간초과 코드 : 

def dfs(L,val) :  
    if L == n :
        candi.add(abs(val))
    else :
        dfs(L+1,val+goosle[L])
        dfs(L+1,val-goosle[L])
        dfs(L+1,val)  
                
if __name__=="__main__" :
    n = int(input())
    goosle = list(map(int,input().split()))
    x = int(input())
    weight = list(map(int,input().split()))
    candi = set()
    dfs(0,0)
    for w in weight :
        if w in candi : print('Y',end=' ')
        else : print('N',end=' ')

 

어떻게 하면 시간을 줄여볼까 고민했지만 

방법이 없는데?!!! 어떻게 줄여야하는지 모르겠다. 

 

 

찾아보니 이 문제는 DFS로 풀면 바로 시간초과다.

AC 하고 싶으면 이차원 DP를 이용해야한다. 

 

 

 

dp를 만들어서 이미 같은 추의 개수로 같은 무게를 만들었으면 return 해줘서 시간 초과를 방지한다. 
왼쪽에 올리거나, 오른쪽에 올리거나, 안올리는 3가지 경우로 나누어 재귀를 사용해서 무게를 defaultdict로 구한다. 

주어진 구하고 싶은 무게들은 defaultdict에 있는지 확인해서 'Y', 'N'를 출력한다. 

 

 

 

정답 코드 : 

def dfs(idx,left,right) :  
    # 모든 추를 확인 
    if idx == n :
        #  지금 무게를 측정할 수 있어요 
        # 그리고 더 추를 넣을 수 없으므로 return 해주기 
        weightDict[abs(left-right)] = True 
        return 
    # idx 번째 추까지 사용했을 때 abs(left - right)무게를 만들 수있니? 
    # 이미 만들어봤으면 그만둬 
    if dp[abs(left-right)][idx] == 1 : return 
    
    
    weightDict[abs(left-right)] = True 
    dp[abs(left-right)][idx] = 1 
    
    # 왼쪽 
    dfs(idx+1,left + weight[idx], right )
    # 오른쪽 
    dfs(idx+1,left, right + weight[idx])
    # 안올림 
    dfs(idx+1,left, right)  
                
if __name__=="__main__" :
    n = int(input())
    # 구슬 무게의 최대가 15000이므로 
    dp = [[0 for _ in range(n+1)] for _ in range(15001)]
    weight = list(map(int,input().split()))
    x = int(input())
    case = list(map(int,input().split()))
    
    weightDict = defaultdict(bool)
    dfs(0,0,0)
    for w in case :
        if weightDict[w] : print('Y',end=' ')
        else : print('N',end=' ')

 

 

 

 

참고 블로그 : 

https://one10004.tistory.com/287

2629. 양팔저울 (Python)