[프로그래머스 - level2] [DFS/BFS] 타겟 넘버

문제 설명

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
[4, 1, 2, 1]	4	2

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

---

 

풀이 과정

dfs -> 스택 -> 후입선출

스택에 배열들을 +양수로 해서 역순으로 넣는다 -> 배열의 맨 첫번째 숫자가 top이 되도록

스택에 들어간 숫자의 합이 target보다 커지면 그 다음 들어올 숫자는 - 

끝쪽에 들어온 숫자를 pop 하고 새로운 top의 부호를 반대로??? 

 

스택으로 하려니까 잘안되서 결국 구글링해서 해당 블로그 참고함

https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84C-BFSDFS

[프로그래머스] 타겟 넘버(BFS,DFS) / C++

 

*참고 

지금까지 연산한 결과에 + / - 연산한 결과를 또 연산하면서 탐색해야 하므로 재귀 방식이 알맞다.

(dfs를 스택보다 재귀를 작성하는 것이 간단)

dfs 트리로 생각한다면

 

numbers.size()와 numbers 벡터의 인덱스를 가리키는 변수인 index 값이 같은 경우가 재귀 함수 종료조건.

모든 원소를 사용하였으며 그 때의 합이 target과 같으면 answer++

재귀함수안에서 numbers 벡터의 다음원소를 더하는 경우 / 빼는 경우를 나누어 재귀적으로 호출.

더하고 빼가며 합을 저장할 sum 변수, numbers 벡터의 인덱스를 참조할 index 변수가 필요 -> 재귀함수의 매개변수로 사용.

=> 재귀적으로 각각의 함수가 리턴되며 answer 값 구할 수 있음.

 

 

코드

#include <string>
#include <vector>

using namespace std;


void recursion(vector<int> numbers,int sum,int index,int target,int* answer)
{
    if(numbers.size() == index)
    {
        if(sum == target)
            ++(*answer);
        return;
    }
    else
    {
        recursion(numbers,sum + numbers[index], index+1,target,answer);
        recursion(numbers,sum - numbers[index], index+1,target,answer);
    }
}


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

 

 

 

알게된 것

- dfs 재귀 구현 : 아직도 조금 모자란 것 같다 다시한번 따로 정리해야 될 듯

 

 

이건 나중에 다시 한번 풀어보자