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

📩 -->문제설명

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 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

💡 solution(사용언어: python)

def solution(numbers, target):
    answer = 0
    lst = [0]
    for num in numbers:
        tmp = []
        for l in lst:
            tmp.append(l+num)
            tmp.append(l-num)
        lst = tmp
    for l in lst:
        if l == target:
            answer += 1
    return answer

👉 설명

• 루트 노드가 0 각 리스트의 0번리스트 부터 양수와 음수일 때 각각 서브트리를 형성하는 그래프라고 생각하고 bfs를 통해 문제를 풀었다.
• [4, 1, 2, 1] 일때 루트 노트 0에서 뻗어나가는 건 +4와 -4가 존재하고 이를 lst에 넣어준다. 이후 +4와 -4에서 각자 뻗어 나가는 것은 +1과 -1이기 때문에 각각 +5, +3과 -3, -5가 뻗어나간다. 결과적으로 lst에는 주어지는 리스트에서 나오는 모든 경우의 값들을 담게 되고 이 값들 중 타겟과 같은 값이 있다면 카운트 해주었다!

🌈 느낀 점

요즘 백준을 풀다가 프로그래머스에 있는 그래프 탐색 문제를 풀고 싶어서 왔는데,, 역시 프로그래머스가 재밌다...

출처: 프로그래머스

오류가 있으면 댓글 달아주세요🙂