[programmers] 타겟 넘버

문제 원본

문제 설명

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

제한사항

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

내 풀이

• 재귀 DFS를 사용했다. 좀 뭔가 바보같이 한 것 같은데.,,

def dfs(numbers, i, res, ans):
    if i == len(numbers):
        return 1 if res == ans else 0
    return dfs(numbers, i+1, res + numbers[i], ans) + dfs(numbers, i+1, res - numbers[i], ans)

def solution(numbers, target):
    answer = dfs(numbers, 0, 0, target)
    return answer

---

처음에 기저 부분 체크하는 거 실수함

if i == len(numbers) - 1: # 리스트의 길이만큼 돌았을 때 (마지막수 연산 안했는데 바로 결과 체크함 ㅜ)
	return 1 if res == ans else 0

이렇게 함 ㅜㅜ ㅋㅋ

식의 답을 체크하는건 마지막 수까지 더하거나 뺀 결과를 보고 할 수 있으니 리스트의 길이 + 1 번째에서 해야한다!

다른 사람의 풀이

나 처럼 dfs()함수를 만들어서 푼 사람들도 많았다.
인자는 어쩔 수 없이 네 개를 사용한 듯.

개쩌는 풀이 하나를 가져왔다.
solution() 함수 자체를 dfs()로 썼다.

찢었다..

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

와 진짜 .. 이런생각을 어떻게 할 수 있는거징?
나도 많이 풀면 이렇게 되겠징