타겟 넘버(8분)

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

구현 아이디어 1분 구현 7분

풀이

핵심 아이디어: 들어온 numbers 배열의 사이즈만큼 +나 -의 조합을 만들면 된다.

1. 부호를 저장할 ch 배열을 선언한다. -1이나 1의 값을 넣어 최종 연산 때 편하게 활용했다.
2. DFS를 이용해 조합을 구한다.
3. numbers 배열 원소에 ch[i]의 원소를 곱해서 전부 더해준다.
4. 값이 target과 같다면 answer를 올린다.

#include <string>
#include <vector>

using namespace std;
int answer = 0;
int T;
int ch[21];
int sign[2] = {-1, 1};

void DFS(int L, int e, const vector<int>& numbers)
{
    if(L == e)
    {
        // ch배열을 보고 숫자에 부호를 붙여서 모두 더했을 때 타겟이 나온다면 answer를 올려준다.
        int sum = 0;
        for(int i = 0; i < numbers.size(); ++i)
            sum += ch[i] * numbers[i];
        
        if(sum == T) ++answer;
    }
    else
    {
        for(int i = 0; i < 2; ++i)
        {
            if(ch[L] == 0)
            {
                ch[L] = sign[i];
                DFS(L + 1, e, numbers);
                ch[L] = 0;
            }
        }
    }
}

int solution(vector<int> numbers, int target) {
    
    int N = numbers.size();
    T = target;
    DFS(0, N, numbers);
    
    return answer;
}

---

개인적인 감상.
조합을 구하는 방법만 안다면 굉장히 쉬운 문제였다. 내 자신감 상승의 날인가? 의도하지 않게 쉬운 문제들만 걸린 기분...

---

역시 잘하는 분들의 풀이는 더 좋다. 빼거나 더하는 조합이기 때문에 재귀함수를 돌릴 때 바로 sum 값을 전해주는 방법이 더 효율적이라 생각이 든다. 다시 풀어본다.

#include <string>
#include <vector>

using namespace std;
int answer = 0;

void DFS(int L, const vector<int>& numbers, int T, int sum)
{
    if(L == numbers.size())
    {
        if(sum == T) ++answer;
    }
    else
    {
        DFS(L + 1, numbers, T, sum + numbers[L]);
        DFS(L + 1, numbers, T, sum - numbers[L]);
    }
}

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

---

추가. 다른 사람의 풀이를 봤을 때 비트를 이용해서 푼 분이 계셨다. 비트 계산을 문제에 활용하는 분들은 정말 대단하다... 공부 해야겠다.