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

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

문제!!

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

예시

numbers	target	return
{1, 1, 1, 1, 1}	3	5

예를 들어 [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

 

---

2. 문제풀이

깊이 우선탐색으로 풀었던 문제입니다. 재귀함수에 대해서 알고 있다면 어느정도 감잡기가 쉬운 문제입니다. 벡터안에 있는 값들을 이용하여 더하기 혹은 빼기로 원하는 값을 맞추는 방법인데요 재귀함수를 이용해서 모든 경우의 수를 체크하면 됩니다. 예를 들어서 {1, 1, 1, 1, 1} 가있다면 아래 코드를 통해  +1 +1 +1 +1 +1 까지 가게되면 모든 숫자를 사용했기때문에 리턴되고 +1 +1 +1 +1 - 1 이됩니다. 이후 리턴하게 되면 다음은 +1 +1 +1 -1 +1 +1 +1 +1 -1 -1 순서가되고 여기서 3이 나오기때문에 카운트가 증가합니다. 이와같이 모든 경우의 수를 찾게되면 끝입니다.

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
using namespace std;
 
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;
}

3.2 주석있는 코드

#include <vector>
using namespace std;
 
//벡터, 정답횟수, 찾아야 하는 숫자, 들어간 깊이, 현재까지 합
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;
}

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
//벡터, 정답횟수, 찾아야 하는 숫자, 들어간 깊이, 현재까지 합
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;
}
 
void print(vector<int> numbers, int target, int answer){
    int t = solution(numbers, target);
    if (t == answer)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print({ 1,1,1,1,1 }, 3, 5);
    return 0;
}

---

4. 결과