[프로그래머스 / C++ / Python] 타겟 넘버

🧩 문제 : 타겟넘버

 

💡 정리

numbers에 주어진 수를 더하고 빼서 target을 만든다.

target을 만드는 방법의 수를 return 한다.

---

 

 

💪🏻 풀이 과정 

🌱 아이디어 

재귀함수로 구현한 dfs로 numbers의 수를 모두 더하고 뺀다. 

재귀함수가 무한루프에 빠지지 않기 위해서 종료 조건이 필요하다. 

• 종료 조건은 numbers의 크기가 index와 같을 때 이다. 즉 모든 원소를 탐색한 경우이다. 
• 모든 원소를 탐색하였는데, sum이 target과 같다면 1을 return 해 target 넘버를 만드는 방법의 수를 구한다. 

재귀함수안에서는 numbers의 다음원소를 더하는 경우와, 빼는 경우를 나누어 재귀적으로 호출한다.

더하고 빼가며 합을 저장할 sum변수와 numbers의 인덱스를 나타내는 index변수가 필요하다.

 

 

numbers = [4, 1, 2, 1]

target = 4 인 경우 그래프는 다음과 같이 탐색할 것이다. 

그래프를 모두 탐색했을 때 (모든 연산을 끝냈을 때) target 값인 4는 두번 등장하므로 1이 두번 return 되어 최종적으로 2가 return 될 것이다. 

 

 

💻 코드

1️⃣ C++

#include <string>
#include <vector>

using namespace std;
int dfs(vector<int> numbers, int target, int index, int sum){
	// 종료 조건 : 모두 탐색한 경우 
    if (numbers.size() == index){
        return sum == target ? 1 : 0;
    }
    // sum에 더하기 연산을 한 경우와 빼기 연산을 한 경우를 합함
    else {
        return dfs(numbers, target, index + 1, sum + numbers[index]) + dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}

int solution(vector<int> numbers, int target) {
    return dfs(numbers, target, 0, 0);
}

2️⃣ Python

def solution(numbers, target):
    return dfs(numbers, target, 0, 0)

def dfs(numbers, target, sum, index):
    if len(numbers) == index:
        return 1 if sum == target else 0
    else:
        return dfs(numbers, target, sum + numbers[index], index + 1) + dfs(numbers, target, sum - numbers[index], index + 1)

 

💭결과