타겟 넘버

첫번째 코드

 

DFS를 이용한 문제인데,

이전에 책으로만 풀어보다가 직접 경험하려해보니 어려움이 있었다.

 

어느정도 코드를 작성한 후 마무리가 되지 않아

다른 사람의 코드를 보고 참고했다.

 

개수를 올려가면서 index == number의 길이 일 때 모든 수를 사용했다는 의미이므로 제한을 둔다.

그리고 target과 여태 더하거나 뺀 total을 비교하여 동일하면 1을 더한다.

numbers안의 수를 더하거나 뺄 때 재귀함수를 사용하여 진행한다.

 

def solution(numbers, target):
    global answer
    answer = 0
    
    def dfs(index, total):
        global answer
        if index == len(numbers):
            if target == total:
                answer += 1
            return
        dfs(index+1, total + numbers[index])
        dfs(index+1, total - numbers[index])
        return
    
    dfs(0, 0)
    
    return answer

 

통과

DFS, BFS가 탈탈 털리는 문제라고 들었는데....

언제쯤 뚝딱 풀 수 있으려나;

---

링크

https://github.com/ornni/programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/43165.%E2%80%85%ED%83%80%EA%B2%9F%E2%80%85%EB%84%98%EB%B2%84

programmers/프로그래머스/2/43165. 타겟 넘버 at main · ornni/programmers