[프로그래머스] 타겟 넘버 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

전체 코드

#include <string>
#include <vector>

using namespace std;
int solve(int cnt, int sum, int target, vector<int>& numbers)
{
    if(cnt==numbers.size())
    {
        if(sum==target)
            return 1;
        return 0;
    }
    
    return solve(cnt+1,sum+numbers[cnt], target, numbers) 
    		+ solve(cnt+1, target, sum-numbers[cnt], numbers);
    
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    answer=solve(0,0, target, numbers);
    
    return answer;
}

 

vector에 들어있는 수를 차례대로 방문하면서 총합 sum에 더하고 빼면서 모든 수들을 사용합니다.

이때, sum과 목표(target)과 비교하며 방법의 수를 계산합니다.

---

 

 

int answer = 0;
answer=solve(0,0, target, numbers);

solve 함수에 차례대로

1. cnt -> 현재 선택한 수의 개수(현재 인덱스)를 기록
2. sum -> cnt만큼 수들을 선택하여 현재 수들을 이용해 덧셈과 뺄셈을 한 결과
3. target -> 타겟 넘버
4. numbers -> 사용할 수들의 배열

을 넘겨줍니다. 이 함수의 결과로 target을 만드는 방법의 수가 반환되어 나옵니다.

이 함수는 BFS를 이용해 경우의 수를 계산합니다.

 

int solve(int cnt, int sum, int target, vector<int>& numbers)
{
	...
}

위의 설명과 동일한 인수를 받습니다.

 

return solve(cnt+1,sum+numbers[cnt], target, numbers) 
            + solve(cnt+1, target, sum-numbers[cnt], numbers);

1. solve(cnt+1,sum+numbers[cnt], target, numbers) 이것의 의미는

cnt번째 수를 sum에 더한 결과(sum+numbers[cnt])를 넘겨줍니다. ( 선택한 수에 + 부호를 붙인다는 뜻 )

이때 cnt번째 수를 계산해주었으니 cnt+1을 넘겨

다음 cnt+1번째 수를 선택하게 합니다.

 

2. solve(cnt+1, target, sum-numbers[cnt], numbers) 이것은

cnt번째 수를 sum에 뺀 결과입니다. 즉  cnt번째 수에 - 부호를 붙여 선택했고 다음 cnt+1번째 수를 선택하러 가겠다는 뜻.

 

 

if(cnt==numbers.size())
{
    if(sum==target)
         return 1;
    return 0;
}

cnt가 수의 개수만큼 되었다면, target과 sum을 비교합니다.

cnt가 number의 크기와 같다면

모든 수를 선택하였고 각각의 수는 덧셈 혹은 뺄셈을 선택하여 sum에 각각 수를 더하거나 빼며 sum에 기록되어있습니다.

sum과 target이 같다면 모든 수를 각각 적절한 덧셈 혹은 뺄셈을 붙여 target을 하나 만들었다는 뜻이므로, 1을 반환합니다.

그게 아니라면 못 만든거니 0을 반환해줍니다.

 

위의 solve 함수의 과정과 결과를 그림으로 표현하자면 아래와 같다.

예로 numbers 에 1, 2, 3 가 들어있고, target으로 4를 들어보겠다.

 

모든 수를 선택하고 원하는 target인 4가 나오는 구간이 하나 있다. 이 트리를 자세히 보겠다.

이때 =4가 나온 곳에서 return 1이, =-2가 나온 곳에서 return 0이 반환되어 나올 것이다.

1과 0을 더한 1이 반환되어 나오고

 

 

그 오른쪽 트리에서는 target이 안 나왔으니 0과 0을 더한 0이 반환된다.

 

이제 또 1과 0을 더한 1이 또 반환되어 나올 것이다.

 

이런 식으로 반환 값들이 타고 올라가게 된다.

 

 

맨 위 시작점에서 0번째 수에 -1을 선택했을때(오른쪽 트리를 탈때) target을 만드는 방법은 1가지로 반환되어 나온다.

마찬가지로 왼쪽으로 트리를 탈 때는

0번째 수에 +1을 선택한 경우로, 똑같은 과정을 거치면 0이 반환되어 나올 것이다.

그래서 예시로 든 경우는 답이 1이 되는 것이다.