Programmers / 타겟 넘버 (DFS) / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 타겟 넘버 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

나의 풀이 (오답...)

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    ch = [0]*n
    
    # v가 나타내는게 
    def DFS(v,n):
        global answer # 전역변수로 사용
        if v == n:
            tmp = 0
            for i in range(1, n):
                if ch[i] == 1:
                    tmp += numbers[i]
                else:
                    tmp -= numbers[i]
            if tmp == target:
                answer += 1
        else:
            ch[v] = 1
            DFS(v+1)
            ch[v] = 0
            DFS(v+1)
    DFS(1,n)
    
    return answer

틀린이유: 인덱스 접근을 어떻게 해야할지 몰라서 대충 막 쳤다...

인덱스와 value전체를 고려하고 하자!

모범답안

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])

def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer

---