[프로그래머스] 타겟 넘버

문제

문제

 

처음 작성한 코드

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

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
    
def solution(numbers, target):
    DFS(0,numbers,target,0)
    return answer

1. 탈출조건: 리스트 끝까지 갔을 때

2. 끝까지 갔는데 target이 됐다? 그럼 answer+=1

3. 쭉쭉쭉 더하면서 가다가 리스트 끝까지 다 갔으면 return 하고 다시 빼기로..

 

깨달은 점

1. 문제를 보고 어떤 알고리즘으로 푸는 게 맞는지 생각하는 능력을 길러야겠다..

2. dfs 풀려고 오랜만에 재귀 생각하니까 재밌었다. 쉬워서 그랬나?

3. 재귀를 풀 때는 항상 탈출조건과 어떻게 돌릴건지를 생각하면 된다.