[프로그래머스 Lv.2 / C++] Day78. 타겟 넘버

2024. 08. 20 - 코딩테스트 스터디 Day78

 
 

01. 문제 설명

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

 
 

02. 제한사항

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

 
 

03. 입출력 예

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 합니다.

 
 

4. 풀이 및 답

#include <string>
#include <vector>

using namespace std;

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

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

 
dfs 함수는 인자로 주어진 숫자 배열 numbers, 목표인 target, 현재 인덱스를 저장하는 변수 index, 현재의 합을 저장하는 변수 sum, 타겟 넘버를 완성한 경우의 수를 저장하는 변수 answer를 받는다.
현재 인덱스와 숫자 배열의 요소 개수가 같을 때까지 dfs를 재귀 호출하면서 numbers 배열 속 수를 더하거나 뺀다. 
현재 인덱스와 숫자 배열의 요소 개수가 같을 때 sum과 target이 같으면 answer를 증가시키고 종료한다.
 
 

정답!

---

요 며칠 dfs, bfs 관련 문제를 연속으로 풀어봤더니
조금 감이 잡힌 것 같기도 하다...