알고리즘/그리디&완탐

[프로그래머스]타켓넘버

안잡아모찌 2019. 10. 25. 19:38

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

완탐.. 흠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <string>
#include <vector>
 
using namespace std;
 
void dfs(int len,vector<int> numbers,int sum,int &cnt,int t){
    if(len==numbers.size()-1){
        if(sum==t) cnt++;
        return;
    }
    dfs(len+1,numbers,sum+numbers[len+1],cnt,t);
    dfs(len+1,numbers,sum+((-1)*numbers[len+1]),cnt,t);
}
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    dfs(0,numbers,numbers[0],answer,target);
    dfs(0,numbers,numbers[0]*(-1),answer,target);
    return answer;
}
cs
저작자표시 비영리 (새창열림)