[프로그래머스] 깊이/너비 우선 탐색 - 타겟 넘버

 

나의 답

from itertools import combinations


def solution(numbers, target):
    answer = 0
    
    for i in range(1, len(numbers) + 1):
        t = list(combinations(numbers, i)) # 조합 생성
        
        for num in t:
            save = numbers.copy() # 주어진 배열 복사
            
            for r in num:
                save.remove(r) # 조합 제외 배열 (주어진 배열 - 조합 배열)
            
            listA = [x * -1 for x in num] # 조합 부분 -1 음수로 설정
            result = listA + save # 조합 제외 배열 (양수) + 조합 부분 (음수) 
            
            if target == sum(result): # 리스트의 합 == 타겟 일경우, count
                answer+=1
        
        

        
    return answer

 

DFS 사용 없이... 조합을 이용해서 풀어봤다.

중복을 허용하는 조합인 리스트를 음수로 관리하고 + 조합 제외 배열이랑 합쳤다.

합쳐진 배열은 모든 경우의 수를 의미하며

이 배열의 합이 타겟 값과 동일하다면 count를 해준다.

 

다른 사람 답

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer

 

와 ... 신기하다...

재귀함수! 저렇게 쓰면 되는구나... 피보나치 수열로만 문제를 풀어보았다 .ㅎㅎ

좀 더 많이 짜봐야겠다..너무 어렵다...^^..