(프로그래머스) 타겟 넘버

문제 링크

• 프로그래머스

요약

• BFS 는 queue 를 활용하자.

최종 §

결과

• Queue 만들어서 BFS 돌렸는데, BP 를 좀 활용했다.
  • 32bit의 상위 16bit에는 누적값을 넣고, 하위 16bit에는 현재의 numbers vector에서의 index 를 넣어서, queue에서 뺀 뒤 다음 값을 더한것과 뺀것을 queue에 다시 넣어주게끔 한다.
• 최종 코드는:

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
#define PACK(acc, idx) (((short)(acc) << 16) | (idx))
#define UNPACK_ACC(pack) ((short)(((pack) >> 16) & 0xFFFF))
#define UNPACK_IDX(pack) ((short)((pack) & 0xFFFF))
 
int solution(vector<int> numbers, int target) {
	queue<int> q;
	int ret = 0;
 
	q.push(PACK(numbers[0], 0));
	q.push(PACK(-numbers[0], 0));
 
	while (!q.empty()) {
		int pack = q.front();
		short acc = UNPACK_ACC(pack);
		short idx = UNPACK_IDX(pack);
 
		q.pop();
		
		if (idx + 1 < numbers.size()) {
			q.push(PACK(acc + numbers[idx + 1], idx + 1));
			q.push(PACK(acc - numbers[idx + 1], idx + 1));
		} else if (acc == target) {
			ret++;
		}
	}
 
	return ret;
}