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

문제 분류 :  DFS/BFS > 타겟넘버

알고리즘  : 깊이 우선탐색 - Depth First Search

작성 언어 :  C++

• 타겟 넘버

문제 설명

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

입출력 예 설명

문제에 나온 예와 같습니다.

 

 

+ 개인적으로 추가한 입출력 예제

[1, 2, 1, 2], 2, 3
[1, 2, 1, 2], 6, 1

 

 

소스코드

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

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

 

ㅡㅡㅡㅡㅡㅡ 개인적인 의견이나 생각 또는 접근법ㅡㅡㅡㅡㅡ

+++++
++++-

+++-+
+++--

++-++
++-+-
++--+
++---

+-+++
+-++-
+-+-+
+-+--

+--++
+--+-
+---+
+----

.....

이러한 패턴을 검사해야한다고 볼때

- 가 1을 , +가 0을 나타낸다고 할때 위에서부터 이진수패턴으로도 볼수있고 (0,1,2,3,4,5, ...  30,31)

 

반복되는 계산을 하지않기위해 sum 의값을 저장해나가며

맨끝에서부터  저장되어있는 sum값 기준으로 연산자 조건을 앞으로 수정해나가며 계산한다고 생각할때

미로찾기에서 끝까지 도달한뒤에 한칸앞으로 되돌아가는 DFS 탐색이 자연스럽게 생각날것이다.

그러면 STACK 과 재귀함수가생각이 날것이고 문제를 풀면된다.

 

이 문제가 값이 커진다면 단순히 반복하는것으로는 해결이 안될것이고

 

SUM 값을 이용하여 이미했던 계산을 다시 반복하지않는것이 중요할것같다.

 

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

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