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

삼성전자 코딩테스트 준비를 하면서 알고리즘 공부를 했지만.. 이런 저런 일로 인해 너무 오래 쉬었다.

잊혀진 기억을 떠올리기 위해 프로그래머스에서 레벨 2 문제를 골랐다

 

문제 링크

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

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

 

문제는 탐색 알고리즘을 이용한 간단한 완전 탐색 문제였다.

주어진 숫자들로 더하기/빼기를 이용해 타겟 넘버를 맞추는 문제다.

 

완전탐색은 for문도 이용할 수 있지만 재귀를 이용한 탐색 알고리즘을 이용한다.

 

예제

numbers	target	return
1,1,1,1	3	5
4,1,2,1	4	2

 

2번 예제의 경우

 

4

(4+1), (4-1)

(4+1+2), (4+1-2), ...

...., (4+1-2+1), (4+1-2-1), ...

 

위와 같이 숫자를 하나씩 누적해가며 다음 숫자를 더하거나 빼면 된다.

DFS를 이용해 +와 -의 케이스를 나눈다.

 

#include <string>
#include <vector>

using namespace std;

int answer;

void dfs(const vector<int> numbers, const int target, int sum, int cnt)
{
    //더해진 값의 개수가 numbers의 개수와 같은 경우 return
    if(cnt == numbers.size())
    {
        //size가 동일하고 더해진 총합이 같은 경우 answer +1 카운팅
        if(sum == target)
        {
            answer++;
        }
        return;
    }
    //더하기
    dfs(numbers, target, sum+numbers[cnt], cnt+1);
    //빼기
    dfs(numbers, target, sum-numbers[cnt], cnt+1);
}

int solution(vector<int> numbers, int target) {
    //answer 값 초기화
    answer=0;
    //탐색 시작
    dfs(numbers, target, 0, 0);
    return answer;
}

 

이전에 DFS를 이용하는 문제를 풀다보면 재귀를 너무 반복해서 error가 발생하는 경우도 있었다.

이를 방지하기 위해 종료조건을 유심히 볼 필요가 있다.

 

이 문제의 경우 더해진 값들의 개수가 vector의 개수와 같은 경우 return하도록 되어있다.

 

level 2의 간단한 문제기 때문에 풀면서 큰 막힘은 없었다..