프로그래머스 타겟 넘버 C++

프로그래머스 : 타겟 넘버

프로그래머스

 

---

- 문제

  BFS를 이용해서 풀 수 있는 문제다.

 

---

- 풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = numbers.size();
    queue<pair<int,int>> q;
    
    q.push(pair<int,int>(numbers[0],1));
    q.push(pair<int,int>(-numbers[0],1));
    
    while(!q.empty()){
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(cnt == size){
            if(num == target){
                answer++;
            }
        }
        else{
            q.push(pair<int,int>(num+numbers[cnt],cnt+1));
            q.push(pair<int,int>(num-numbers[cnt],cnt+1));
        }
    }
    return answer;
}

 

 

bfs를 이용해서 +와 - 둘다 해주면서 cnt를 이용해 크기가 일정 크기 이상 커지지 않게 하면서 answer를 하나씩 더해주면서 풀면 된다.

 

  

---

- 기억할 것!

 X