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

문제 설명

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

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

총 2가지 방법이 있으므로, 2를 return 합니다.

---

풀이

# +로 들어오거나 -로 들어오거나 => BFS로 모든 경우 탐색
def solution(numbers, target):
    ans = 0
    results = [0] # 덧셈 결과
    for n in numbers:
        # print(f"now results : {results}")
        ar = [] # 현재 레벨의 노드들의 연산 결과
        for r in results: # 부모 노드들의 연산 결과에 현재 노드들의 노드들을 덧셈
            ar.append(r+n)
            ar.append(r-n)
        # print(f"now ar : {ar}")
        results = ar #현재레벨에서의 연산이 끝났으므로 results에 결과 붙여넣기
    for r in results: #target에 걸맞는 연산결과 탐색
        if r == target:
            ans += 1
    return ans

참고: https://velog.io/@timointhebush/프로그래머스-타겟-넘버-DFS-BFS-Python

아무리 DFS/BFS 개념공부를 했지만 아이디어가 영 떠오르지를 않았다.
첫 번째 주석에 쓴 +로 들어오거나 -로 들어오거나 라는 생각을 초장에 하긴 했는데
그래서 이걸 DFS/BFS로 어떻게 구현하는데..? 싶었다.

결국 구글링했고 BFS를 이용하여 나이스하게 풀 수 있는 코드를 발견했다.

그림 풀이

코드를 봐도 한 번에 이해가 가질 않아 그림으로 그려봤는데, 이 구조에 맞게 각 노드의 덧셈 결과를 results 리스트에 담으려는 것이 주 목적이다.

결과

남의 코드

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])

좀 오래걸리긴 하는데 코드가 워낙 간결해서...

return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

이부분 발상 너무 좋다. numbers에서 첫 숫자를 target과 +로 더하거나 -로 더한 다음, 첫 번째 숫자를 뺀 부분을 넘겨버린다!

결국 numbers가 없어지고 target이 0이 된다는 것은 올바른 결과에 봉착한것이므로 1을 반환하여 더하게끔 한다.
target이 0이 되지 않았는데 numbers가 없어지지 않았다는 것은 틀린 연산이라는 뜻이다.

후기

참고한 블로그를 보면 DFS 코드도 써 놓으셨다. 그런데 나는 봐도 이해가 안된다ㅋㅋㅋ
내가 재귀를 너무 어려워해서 그런 것 같다.. 함수 호출이 반복되다보면 정신줄을 놓게 돼서..ㅠㅠ
이해해보려고 그림도 그려봤는데 그래도 잘 모르겠슴