타겟넘버: DFS 풀이

타겟 넘버

문제 설명

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

풀이1

answer = 0

def calc(index, numbers, target, value):
    global answer;

    if(index==len(numbers)):
        if(value==target):
            answer += 1
            return
        return

    calc(index+1, numbers, target, value+numbers[index])
    calc(index+1, numbers, target, value-numbers[index])

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

파이썬에서 return은 함수를 바로 종료시키는 명령어다.

종료시키지 않는다면, 무한 재귀를 돌 것이다.

이 풀이의 핵심은

1. 더하거나 뺀다는 것을, 이진트리로 보는 것

2. 사칙연산을 전체 노드의 방문으로 보는 것

3. 인덱스의 증가와, 값이 연산을, 매게변수로 전달했다는 것

풀이2

def solution(numbers, target):
	if not numbers and target ==0 :
		reutrn 1
    elif not numbers :
    	return 0
    else return solution(numbers[1:],target+numbers[0])+solution(numbers[1:],target-numbers[0])

이 풀이의 핵심은

배열의 요소를 더하거나 뺀 값의 합이 target과 같다는 식을 이항하여

target - sum = 0으로 본 것.

하루 지난 나의 풀이

answer = 0

def DFS(numbers, target, value):
    global answer;
    if not numbers:
        if value == target:
            answer +=1
        return

    else :
        DFS(numbers[1:], target, value+numbers[0])
        DFS(numbers[1:], target, value-numbers[0])

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

굳이 인데스를 매게변수로 줄 필요 없다.

numbers[1:]로 재귀하면 끝은 빈 배열이 남기 때문이다.

1번과 2번을 짬뽕해서

직관성과 간결성을 모두 챙겼다.

최대한 풀어본 문제를 외워서 해결하려고 하기 보다,

이 문제를 어떤 추상적 구조로 풀었지를 생각하며 푼 결과다.