프로그래머스 | 타겟 넘버 (Python)

프로그래머스

 

알고리즘 고득점 키트 dfs/bfs 유형의 문제인데 그냥 combinations 써서 풀었다..

 

내 코드

from itertools import product

def solution(numbers, target):
    count = 0
    length = len(numbers)
    
    for ops in product('-+', repeat=length):
        tmp = 0
        for i, op in enumerate(ops):
            if op == '-':
                tmp -= numbers[i]
            else:
                tmp += numbers[i]
        
        if tmp == target:
            count += 1
    
    return count

 

dfs 활용 코드

def solution(numbers, target):
    def dfs(index, current_sum):
        # 모든 숫자를 다 사용한 경우
        if index == len(numbers):
            # 현재 합계가 목표 값과 같은지 확인
            return 1 if current_sum == target else 0
        
        # 현재 숫자를 더하는 경우와 빼는 경우 두 가지로 나눠서 탐색
        add = dfs(index + 1, current_sum + numbers[index])
        subtract = dfs(index + 1, current_sum - numbers[index])
        
        # 두 가지 경우의 합을 리턴
        return add + subtract
    
    # DFS 시작: 첫 번째 숫자부터 시작해서 탐색
    return dfs(0, 0)