[프로그래머스 / Level 2] 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버

numbers의 길이가 20개 이하라는 점과 가능한 연산의 수가 +, - 두 가지라는 점을 먼저 생각해야 합니다.

이것은 모든 케이스에 대해서 계산해도 2의 20승인 1,048,576이므로 시간초과가 발생하지 않는 것을 알 수 있습니다.

 

문제 접근법

• number 배열에 있는 값들을 재귀함수를 이용하여 모든 계산할 수 있는 케이스에 대해서 시행해본다.
• 진행한 횟수가 nubers의 길이만큼이라면 계산한 값이 target과 일치하는지 확인한다
  • 일치할 경우 answer을 증가시킨다.
  • 아닐 경우 함수를 종료시킨다.

 

아래는 코드입니다.

#include <string>
#include <vector>
 
using namespace std;
 
int answer = 0;
int t;
vector<int> num;
 
void Calculate(int sum, int index, int nLen)
{
    if (index == nLen)
    {
        if (sum == t)
            answer++;
        
        return;
    }
    
    Calculate(sum + num[index], index + 1, nLen);
    Calculate(sum - num[index], index + 1, nLen);
}
 
int solution(vector<int> numbers, int target) {
    int len = numbers.size();
    t = target;
    num = numbers;
    
    Calculate(0, 0, len);
    
    return answer;
}