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

문제 설명

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, 1, 1, 1, 1]

3

5

접근법

DFS/BFS 문제임을 알고 켰음에도 도저히 적용 법이 떠오르지 않아 나의 한계를 느끼게 해 준 문제였다. 다른 사람의 접근법을 보며 문제를 해결했는데, 이런 방식으로 트리를 만들고 해결할 수도 있구나 라는 걸 느꼈다. 우선 해당 문제는 DFS로 해결하는데...

위와 같이 트리가 있다고 가정할 때, 트리를 한층 한층 밑으로 만들어 나가는 느낌이라고 보면될 것 같다. 한 노드에 숫자를 빼고 더한 결과를 자식 노드로 쌓는다.

내 코드

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)

tree의 첫 번째 층에는 0을 넣어준다.

tree는 이전 수에 대한 계산 결과를 담은 층을 가지고 있고, sub_tree는 현재 숫자에 대한 결과를 담은 자식 노드를 하나씩 추가하는 역할을 한다.

바깥 for문은 매개변수로 받은 숫자 목록을 하나씩 꺼내와 주는 역할을 한다.

내부 for문은 노드 하나하나에 숫자를 더하고 빼주어 자식 노드들을 생성하는 역할을 한다. 

솔직히 이번 문제는 다른 풀이의 도움을 많이 받아서 풀었기 때문에 자신에게 실망을 많이 했다. 다른 사람의 풀이를 보고도 열심히 그리면서 이해했다 ㅠㅠ 아무래도 문제를 읽고 해결책을 도출하는 능력을 길러야 할 것 같다.