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

아직 dfs 개념이 제대로 안잡혀있는 것 같아 다시 정리해봅니다. 

 

💡 문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

입출력 예 설명

 

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

 

타겟 넘버 

프로그래머스

 

---

🙆🏻‍♀️ How to Solve

이 문제는 dfs/ bfs 모두 풀 수 있는 문제이다. 

 

내가 생각한 방법은 dfs로 푸는 방법이였다. 

 

이렇게 깊이 탐색으로 모든 숫자를 다 더하고 빼는 경우를 구한 뒤, 마지막에 계산된 숫자가 target 수와 같다면 count 값을 +1 해주는 식으로 생각하였다. 

 

(여기서 주의할 점은, 첫번째 숫자도 +인 경우와 -인 경우 모두 고려하여 구해야한다.) 

 

💻 CODE

count = 0 #총 개수 구하기위한 변수 

def dfs(i, result, numbers, target) : #i= 깊이(숫자를 끝까지 사용했는지 보기 위해), result = 마지막에 계산된 수 
    global count 
    if i == len(numbers) : #제시된 수를 끝까지 사용하였다면(깊이가 끝까지 탐색하였다면)  
        if result == target : #계산된 숫자와 target 값이 같다면 
            count+=1 #총 개수를 늘려줌 
            return
    else : #깊이가 끝까지 안됐으면
        dfs(i+1, result+numbers[i], numbers, target) #그 다음 수를 +하여 다시 dfs 탐색
        dfs(i+1, result-numbers[i], numbers, target) #그 다음 수를 -하여 다시 dfs 탐색

def solution(numbers, target):
    result = 0
    dfs(0, result, numbers, target) 
    
    return count