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

문제

프로그래머스 DFS/BFS - 타겟 넘버 (Level 2)

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

 

---

문제 풀이

접근 방식

주어진 배열의 숫자들을 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 구하는 문제이다.이 문제는 BFS 방식으로 해결해주었다.

 

우선, 결괏값을 저장할 배열인 answer_list에 0을 넣어주었고,그 배열의 값에 numbers[i]를 더한 값과 뺀 값을 temp에 넣어주었다.temp에 저장된 결괏값들은 answer_list에 다시 복사해주었다.이 과정을 numbers의 원소의 개수만큼 반복해주었다.이후, 최종 결괏값 배열인 answer_list에서 타겟 넘버의 개수를 세서 답을 구해주었다.

 

---

풀이 코드 - C++

#include <vector>
using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    vector<int> answer_list(1);
    for(int i : numbers){
        vector<int> temp;
        for(int j : answer_list){
            temp.push_back(j+i);
            temp.push_back(j-i);
        }
        answer_list = temp;
    }
    for(int i : answer_list) {
        if(i == target)
            answer++;
    }
    return answer;
}

실행 결과

실행 결과 : 100.0