[프로그래머스] [C++] 타겟 넘버 (dp, dfs)

1. 문제

 

사용할 수 있는 숫자들과 타겟 넘버가 주어진다.

 

사용할 수 있는 숫자들 모두 사용하여 타겟넘버를 만들어라

 

단, 이때 연산은 +, - 만 가능하다.

 

2. 핵심

이 문제의 핵심은 사용할 수 있는 숫자들 모두를 사용하는 것이다.

 

처음에는 순서도 포함하여 세는줄 알았지만 순서는 필요없다는 것

 

그냥 숫자를 사용하기만 하면된다는 것이다.

 

모든 숫자를 사용해야하므로 재귀를 통해 모든 숫자를 탐색하면서

 

+ 이나 - 를 해주며 마지막 숫자일때 타겟넘버와 동일한지 검사한다.

 

이는 dfs형태로 이루어지며

 

혹시모를 겹치는 부분을 대비하여 dp 를 적용시킬 수 있다.

(실제로 테스트 1 과 테스트 2의 경우 시간이 빨라진다.)

3. 코드

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
int cache[2001][20];
int dfs(int here, const vector<int>& numbers, const int& target, int sum)
{
    int& ret = cache[1000 + sum][here];
    if(ret != -1) return ret;
    if(here == numbers.size())
        if(sum == target) return 1;
        else return 0;
    
    ret = 0;
    ret += dfs(here + 1, numbers, target, sum + numbers[here]);
    ret += dfs(here + 1, numbers, target, sum - numbers[here]);
    
    return ret;
}
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
    memset(cache, -1, sizeof cache);
    answer = dfs(0, numbers, target, 0);
    
    return answer;
}

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

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

Algorithm/TargetNumber.cpp at master · Nor-s/Algorithm (github.com)

Nor-s/Algorithm