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

안녕하세요 뚜디 입니다

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 (programmers.co.kr)

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

< 프로그래머스 - 타겟 넘버 (LV2) >

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

1. 연습 문제

※ 문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

※ 제한 조건

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

※ 입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

2. 문제 풀이

해당 문제는 DFS or BFS 풀이로 접근하도록 문제에서 알려주고있습니다.
하지만 저도 DFS/BFS 알고리즘 문제는 아직도 익숙하지가 않네요... 너무 어려워요... 공부 부족...

DFS(깊이 우선) 풀이 같은 경우,
임의의 벡터의 마지막 인자값까지 더하고 빼서 타겟값을 만드는 경우의 수를 찾도록 구현할수 있다.
BFS(너비 우선) 풀이 같은 경우,
큐를 생성하여 초기값으로 임의의 벡터 첫번째 인자의 양수 값, 음수 값을 통해 초기화하영 진행
큐에 저장된 인자 중 가장 앞 인자값을 빼서(Q.pop) 나머지 인자 값에 더하고, 빼준다<- 이과정을 반복

※ DFS

• DFS(깊이우선탐색): 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
• 주로 스택 또는 재귀함수로 구현

출처 :&nbsp;TWpower's Tech Blog

※ BFS

• BFS(너비우선탐색): 현재 정점에 연결된 가까운 점들부터 탐색
• 주로 큐로 구현

출처 :&nbsp;TWpower's Tech Blog

 

3. 소스 코드

※ DFS(재귀)

#include <string>
#include <vector>

using namespace std;

///DFS풀이

void dfs(vector<int>& numbers, int& answer, int target, int count = 0, int sum = 0) {
    if(count == numbers.size() - 1) {
        if(target == sum + numbers[count]) {
            answer++;
        }
        if(target == sum - numbers[count]) {
            answer++;
        }
        return;
    }
    dfs(numbers, answer, target, count + 1, sum + numbers[count]);
    dfs(numbers, answer, target, count + 1, sum - numbers[count]);
}

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

※ BFS(큐)

#include <string>
#include <vector>

using namespace std;

///BFS풀이
#include<queue>

int solution(vector<int> numbers, int target) {
    int answer = 0;
    queue<int> q;
    q.push(numbers[0]);
    q.push(-1 * numbers[0]);
    
    for (int i = 1; i < numbers.size(); i++) {
        int len = q.size();
        for (int j = 0; j < len; j++) {
            int sum = q.front();
            q.pop();
            q.push(sum + numbers[i]);
            q.push(sum - numbers[i]);
        }
    }
    
    int qsize = q.size();
    for (int i = 0; i < qsize; i++) {
        if (q.front() == target)
            answer++;
        q.pop();
    }
    return answer;
}

 

4. 결과

※ DFS풀이

※ BFS풀이