[Python : 프로그래머스] 타겟 넘버

문제

https://programmers.co.kr/learn/courses/30/lessons/43165

풀이

def solution(numbers, target):
    from itertools import product
    pm = [(num, -num) for num in numbers]
    answer = list(map(sum, product(*pm)))
    return answer.count(target)

itertools를 워낙 자주 사용했었기 때문에,
문제를 보자마자 “아 드디어 product를!” 라는 생각으로 시작했다.

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

라는 가정만 있었을 뿐, 어떠한 규칙이 있다는 말이 없었기 때문에
양의 정수와 음의 정수를 하나씩 짝맞춰 옮겨 담았고,
이걸 product함수를 이용해 모든 조합을 구했다.
그리고 거기서 target에 해당하는 값 개수만 반환.

더 나은 풀이

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

재귀로 풀었는데… 재귀끼리 더해지는걸 보면 분할정복인가?
알고리즘의 꽃은 재귀라는 말이 있던데, 확실히 손으로 직접 풀어보면
“와 이걸 어떻게 생각한거지?” 싶긴 하다.

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

대표적인 DFS 풀이. 가장 교과서적인 코드인 것 같다.
python이 아닌 다른 언어로 짠다면 이렇게 짜는게 옳아 보인다.
DFS/BFS 재귀풀이 연습 좀 해야겠다.