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

문제 설명

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

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

문제 보기

생각 과정
1. dfs/bfs 문제라는 것을 알고있었는데도 불구하고 제대로 된 풀이법을 생각해내지 못했다. 코딩테스트스러운 사고를 아직,, 😂
2. 모든 경우의 수를 만들어서 숫자를 세야겠다는 생각 자체를 못한 것같다. 그래서 더욱 어려워지고 복잡스러워졌던 것 같다.

문제 풀이

def solution(numbers, target):
    
    tree=[0]
    for num in numbers:
        sub_tree=[]
        for tree_num in tree:
            sub_tree.append(tree_num+num)
            sub_tree.append(tree_num-num)
        tree=sub_tree

    return tree.count(target)

사실상 내가 쓴 코드는 아니다. 구글링을 해본 결과 내가 가장 이해하기 쉬웠던 코드이다.

• numbers를 + , - 하나씩 다 계산해서 트리를 만들 것.
• tree 는 내가 만들고 싶은 최종적인 트리이고, sub_tree는 tree를 완성시키기 위한 보조 트리이다.
• bfs를 이용했다.
  코드 출처

다른 사람 풀이

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

재귀를 이용하는,,!!