[level2] 타겟 넘버

1. 문제

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

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

 

제한사항

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

 

 

 

---

2. 문제 풀이 

 

가능한 모든 경우의 수를 조회하는 문제이므로 dfs 문제로 풀 수 있다. 

 

1) answer를 전역 변수로 정의한 후, 0으로 초기화한다. 

2) dfs 함수를 호출한다. 이때, 주어진 numbers배열과 target 변수와 함께 idx와 values를 각각 0으로 초기화하여 함께 전달한다. 

• idx: 깊이 확인(주어진 numbers의 개수 만큼 진행했는지) + 주어진 배열에 차례대로 접근 
• values: number[idx]를 더하거나 뺀 총 값
  • 즉, 주어진 하나의 숫자에 대해 더하기 혹은 빼기를 진행한 값 

3) dfs 함수에서도 answer를 전역 변수로 정의한다. 

4) 만약 idx의 길이가 numbers의 길이와 같고 (= 하나의 경우의 수 탐색 완료), 그 값이 target과 같다면 answer에 1을 더하고 return한다. 

5) 만약 idx의 길이가 numbers의 길이와 같기만 한다면, 하나의 경우의 수가 탐색 완료된 것이므로 return한다. 

6) idx의 길이가 numbers의 길이와 같지 않다면, 아직 하나의 경우의 수가 탐색 완료 되지 않은것이므로 dfs 함수를 호출한다. 

이때, idx에 각각 1을 더해 다음 수를 탐색하게 하고, values에 해당 값을 더하거나 빼어 각각의 경우의 수에 대해 탐색을 가능하게 한다. 

def dfs(numbers, target, idx, values):
    global answer 
    
    if len(numbers) == idx and values == target:
        answer += 1
        return 
    elif len(numbers) == idx:
        return 
    
    dfs(numbers, target, idx+1, values+numbers[idx])
    dfs(numbers, target, idx+1, values-numbers[idx])

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

 

저번에 dfs문제 백준에서 풀 때 비슷한 문제 풀었는데

기억을 못해서...구글링의 힘을 얻었다...

다시 풀어봐야지