Programmers : 타겟넘버(C++)

programmers.co.kr/learn/courses/30/lessons/43165

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

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) BFS를 이용하면 쉽게 풀 수 있는 문제이다.

2) value와 level을 이용해서 dfs를 순환 시킨다. 이때 level이 numbers 배열의 size와 같아질 때, target과 value의 값이 같으면 answer를 증가 시킨다.

3) level이 numbers 배열의 size와 같아지는 경우 새로운 값을 넣을 필요가 없으므로 continue 해준다.

4) queue에 새로운 값을 넣을 때는 +,- 값을 모두 넣어준다.

 

#include <string>
#include <vector>
#include <queue>
using namespace std;



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

        
    }
    return answer;
}

주의사항)

level이 numbers 배열의 size와 같아지는 경우 새로운 값을 넣을 필요가 없으므로 continue 해주지 않으면, 필요 없는 계산이 많아질 수 있다.