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

문제 파악

음이 아닌 n개의 정수들을

순서를 바꾸지 않고

더하거나 빼서

타겟 넘버를 만든다.

 

---

유형 파악

우선 문제에서 주어진 입출력 예를 보고 직접 하나하나 구해보자.

 

 

numbers를 통해 주어진 수들이 순서대로 더해지거나 빼지는 것이므로 아래 그림과 같이 모든 경우를 직접 구해본다.

 

첫 번째 입출력 예

numbers에 주어진 수 5가지를 순서대로 더하거나 빼준다.

마지막에 target 값인 3이 나오는 경우가 총 5가지인 것을 확인할 수 있다.

 

 

 

두번째 입출력 예

numbers에 주어진 수 4가지를 순서대로 더하거나 빼준다.

마지막에 target 값인 4가 나오는 경우가 2가지인 것을 확인할 수 있다.

 

🤨

두 가지의 입출력 예에 대해 직접 그려본 결과 

연산한 결과에 대해 계속해서 + 또는 - 연산을 반복하며 탐색하는 것을 확인할 수 있다.

DFS(깊이 우선 탐색)를 통해 모든 경우의 수를 탐색하면 된다.

이는 재귀 함수를 통해 구현할 수 있다!

 

---

DFS: 재귀함수로 구현하기

numbers에 있는 숫자들을 더하고 빼서 sum을 만든 후 해당 숫자가 target과 일치한 경우 answer을 1 증가시켜주면 된다.

 

1. 재귀함수를 정의한다. 이때 numbers 배열의 인덱스를 표현하는 idx와 현재까지 숫자를 더하고 빼서 만들어진 값을 표현하는 sum을 매개변수로 둔다.
2. sum 값에 numbers[idx] 값을 더하는 경우와 빼는 경우를 나누어 재귀함수를 호출한다. 그러면 위 그림에서 처럼 트리가 두 방향으로 나누어지는 것이다. 이 과정을 계속 반복한다.
3. 깊이우선탐색을 할 것이므로 마지막 숫자를 더하거나 뺀 후에는 return해 주어야 한다. 이는 idx 값이 number의 마지막 원소를 가리키지는지 확인을 통해 알 수 있다. 또한 이 때 return하기 이전에 sum 값이 target 값과 일치하면 answer를 1증가시켜 준다.

---

코드

➕ 재귀함수 안에서 idx를 먼저 증가시킨 후 숫자를 더하거나 빼므로 idx를 -1부터 시작

 

#include <string>
#include <vector>

using namespace std;

int answer=0, t;
vector<int> num;

void dfs(int idx, int sum){
    if(idx==num.size()-1){
        if(sum==t){
            answer++;
        }
    } else{
        idx++;
        dfs(idx, sum+num[idx]); // num의 숫자를 더하는 경우 재귀함수 호출
        dfs(idx, sum-num[idx]); // num의 숫자를 빼는 경우 재귀함수 호출
    }
}

int solution(vector<int> numbers, int target) {
    t=target;
    num=numbers;
    
    dfs(-1, 0);
    
    return answer;
}