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
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])
와 진짜 .. 이런생각을 어떻게 할 수 있는거징?
나도 많이 풀면 이렇게 되겠징