프로그래머스 > 타겟 넘버 (Python 3)

1. 문제 설명

n개의 음이 아닌 정수들이 있다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다.

 

(1) -1+1+1+1+1 = 3

(2) +1-1+1+1+1 = 3

(3) +1+1-1+1+1 = 3

(4) +1+1+1-1+1 = 3

(5) +1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하라.

 

 

 

2. 코드

answer = 0

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

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

 

 

 

3. 설명

전형적인 깊이 우선 탐색 (DFS) 문제이다.

 

우선 solution에서 numbers 배열과 target, 시작하는 인덱스 번호인 0, 빼고 더한 결과를 저장하는 result에 0을 담아서 DFS 함수에 전달한다.

전역변수 (global) answer를 사용해서, 만약 numbers의 모든 원소를 다 한 번씩 더하거나 뺐고 그 결과가 타겟 넘버와 같다면 answer을 1 키우고 함수를 종료한다.

 

그렇지 않은 경우에는 현재 인덱스의 원소를 더한 값, 뺀 값을 각각 재귀함수로 호출하여 연산을 수행한다.