[Programmers] 타겟 넘버

yunan·2020년 9월 17일

programmers

🐬 알고리즘 풀이 🐬

목록 보기

6/74

🔦 문제 링크

✍️ 풀이

C++ 처럼 DFS를 이용해서 풀려고 했으나 global이라는 것을 알지 못했다.
리스트의 크기 만큼 더했을 때 target과 값이 같으면 global answer 1 증가
아니라면 아무것도 하지 않고 함수를 빠져나온다.

주의사항
- 바같에 answer 선언 후 함수 내 global로 선언

🛠 전역 변수 쓴 코드

# 전역변수를 쓰려면 global을 사용해야한다.
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

✍️ 전역 변수 안 쓴 풀이

ret 변수에 조건을 만족하는 모든 갯수를 더한다.
ret 의 흐름에 대해서 기억하자.

🛠 코드

# 전역변수 안 쓴 답
def dfs(num, t , s, count):
    ret = 0
    if len(num) == count:
        if t == s:
            return 1
        else:
            return 0
    ret+=dfs(num,t,s+num[count],count+1)
    ret+=dfs(num,t,s-num[count],count+1)
    return ret
def solution(numbers, target):
    answer = 0
    answer=dfs(numbers, target, 0, 0)
    return answer