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

분류 : bfs/dfs

 

요구사항

주어진 숫자들과 +, - 연산을 이용하여 target 숫자 만들기

 

풀이

bfs로 풀어보았다.

position과 sum을 index로 가지는 큐를 만들어서

현재 position의 값을 +, - 해준뒤 position을 하나 증가시켜 큐에 넣어서 풀었다

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct go {
	int pos;
	int sum;
};

int solution(vector<int> numbers, int target) {
	int answer = 0;
	queue<go> q;
	int lastpos = numbers.size();
	q.push({ 0,0 });
	while (!q.empty()) {
		int nowpos = q.front().pos;
		int nowsum = q.front().sum;
		q.pop();
		if (nowpos == lastpos && nowsum == target) {
			answer++;
			continue;
		}
		if (nowpos == lastpos) {
			continue;
		}
		for (int i = 0; i < 2; i++) {
			int nextsum;
			if (i == 0) {
				nextsum = nowsum + numbers[nowpos];
			}
			else if (i == 1) {
				nextsum = nowsum - numbers[nowpos];
			}
			q.push({ nowpos + 1,nextsum });
		}
	}
	return answer;
}