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

안녕하세요, DFS/BFS로 돌아온 쏘코입니다.

뒤로 갈수록 level과 다르게 익숙하지 않은 부분들이 많아서 문제들이 어렵네요.. (분명 자료구조시간에 공부했음에도 불구하고!!!!!)

이번 문제도 바로 살펴보시죠!

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43165

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

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

0. 문제 설명

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 함수를 작성해주세요.

0.0. 제한사항

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

0.1. 입출력 예

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

0.2. 입출력 예 설명

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

1. 풀이 과정

문제를 읽고 가장 먼저 든 생각은 이 문제가 여기 있는게 맞나..??였습니다.

그래도 DFS/BFS 코너에 있으니 DFS로 풀어봐야겠다라고 생각하고, 재귀적 방법으로 생각했습니다.

먼저 numbers와 target을 받아왔기 때문에 이걸 이용할 생각을 했습니다.

각 numbers에서 + - 한것들을 따로 저장해서 재귀함수로 돌리면 되지 않을까?? 하는 아이디어를 만들었고, 그대로 만들었습니다. 그 과정에서 필요했던 내용은 numbers의 개수와 현재 idx였습니다. numbers의 모든 원소들을 한번씩은 사용해야 했고, 그렇기 때문에 idx는 size만큼 돌아야 했습니다.

solution에서는 size, idx, sum의 정의만 해주고 바로 dfs라는 함수가 돌아가도록 만들었습니다.

그렇다면 이제 dfs라는 함수를 만들어야겠죠?

dfs에는 총 5가지의 parameter가 들어가도록 만들었습니다. 처음에는 numbers라는 vector를 받고, 이 vector에 접근할 idx 변수, 연산 후 남은 결과를 저장할 sum 변수, idx가 무한히 증가하게 만들 수는 없으니 size변수도 넣어주고, target이 되는 수도 넣어줬습니다.

(여기서 vector, size, target는 고정값이므로 반드시 파라미터로 받아야 하는 것은 아닙니다. 편하신 대로 조정하시면 됩니다.)

dfs 함수 내에서 가장 먼저 한 일은 temp와 temp2를 만든 것입니다. temp와 temp2는 각각 sum에다가 numbers[idx]를 더하고 뺀 값을 넣어줬습니다.

이 temp와 temp2이 target과 일치하는 지 확인합니다.

그리고 idx와 size-1을 비교합니다. 우리는 vector로 받은 값을 모두 사용해야 하기 때문에, 다 사용하지 않고 target이 된 경우를 걸러야 하기 때문입니다. (이 부분때문에 한 10분 고민했습니다..)

이 두 가지 조건을 모두 만족하는 경우 answer를 1 늘려줍니다. 우리가 answer를 따로 받아오지 않았기 때문에 저는 global 변수로 solution함수 밖에 만들었습니다. 만약 이 부분도 global변수를 쓰지 않고 싶으신 경우에는 파라미터 값으로 받으시면 됩니다.

이 작업을 모두 완료한 경우 다음 재귀함수를 위해서 idx+1이 size보다 작은지 확인합니다. 그래야 우리가 참조할 값이 있을 거니까요. 만약 idx+1이 더 작으면 dfs를 돌립니다. 두 번째 파라미터의 idx값을 1추가하고, sum자리에는 우리가 아까 더하고 빼준 temp와 temp2값을 넣어줍니다. 이렇게만 하면 전체 solution.cpp 작성은 완료됩니다.

2. 소스 코드

#include <string>
#include <vector>

using namespace std;
int answer = 0;

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