-

[프로그래머스] 레벨 2 - 타겟 넘버 본문

1-4. 프로그래머스

[프로그래머스] 레벨 2 - 타겟 넘버

asdklfjlasdlfkj 2020. 2. 7. 21:01

https://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+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘

programmers.co.kr

전형적인 DFS 문제다. 

현재 인덱스의 숫자를 더한 것의 재귀와

현재 인덱스의 숫자를 뺀 것의 재귀를 이어나가 최종 길이만큼 연산을 수행한 뒤, 결과를 tg_num과 비교해 답을 추가한다.

 

100번째 포스팅!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
#include <vector>
 
using namespace std;
int answer = 0;
int tg_num;
int length;
vector<int> number;
void dfs(int idx, int num){
    if(idx == length){
        if(num == tg_num){
            answer++;
        }
        return;
    }
    int curnum = number[idx];
    dfs(idx+1, num+curnum);
    dfs(idx+1, num-curnum);
}
 
int solution(vector<int> numbers, int target) {
    length = numbers.size();
    for(int i=0; i<numbers.size(); i++) number.push_back(numbers[i]);
    tg_num = target;
    dfs(00);    
    return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

Comments