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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

 

해결전략

 

DFS

BFS

DP

 

---

 

처음 시도한 코드 DFS  -  시간초과

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int answer; // 타겟 넘버를 만드는 방법의 수
int ch[1001]; // 방문 체크 배열
 
void DFS(int x, int sum, int target, vector<int>& numbers)
{
    if(x == numbers.size()){
        if(sum == target){
            answer++;
        }
        return;
    }
 
    for(int i=x; i<numbers.size(); i++)
    {
	    if(ch[i]==0)
	    {
            ch[i] = 1;
            DFS(x + 1, sum + numbers[i], target, numbers);
            DFS(x + 1, sum - numbers[i], target, numbers);
            ch[i] = 0;
	    }
    }
}
 
int solution(vector<int> numbers, int target) {
  
    DFS(0, 0, target, numbers);
 
    return answer;
}
 
int main()
{
    vector<int> testcase1 = { 1, 1, 1, 1, 1 };
    vector<int> testcase2 = { 4, 1, 2, 1 };
 
    cout << solution(testcase2, 4);
 
    return 0;
}

 

---

 

정답 코드 DFS -  첫번째 코드에서 불필요한 부분을 제거

 

#include <string>
#include <vector>
using namespace std;
 
int answer; // 타겟 넘버를 만드는 방법의 수
 
void DFS(int x, int sum, int target, vector<int>& numbers)
{
    if(x == numbers.size()){
        if(sum == target){
            answer++;
        }
        return;
    }
       
    DFS(x + 1, sum + numbers[x], target, numbers);
    DFS(x + 1, sum - numbers[x], target, numbers);   
}
 
int solution(vector<int> numbers, int target) {
  
    DFS(0, 0, target, numbers);
 
    return answer;
}

이 문제에서는 -, + 두 가지 경우만 고려해서 DFS 가지가 뻣어나간다. 따라서 for문으로 방문체크가 굳이 필요하지 않다. for문을 없애니 실행속도가 크게 향상되었다.

 

---

 

정답코드 BFS 

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int answer; // 타겟 넘버를 만드는 방법의 수
queue<pair<int,int>> Q; //pair<int,int>: 현재 인덱스, 숫자들의 합
 
void BFS(vector<int>& nums, int target)
{
    Q.push({ 0,-nums[0] });   // - 넣기
    Q.push({ 0,nums[0] }); // + 넣기
 
    while (!Q.empty()) {
        int idx = Q.front().first;
        int total = Q.front().second;
        Q.pop();
 
        if (idx == nums.size() - 1 && total == target) {
            answer++;
            continue;
        }
        if (idx == nums.size() - 1 && total != target) {
            continue;
        }
               
        Q.push({ idx + 1, total + (-1 * nums[idx + 1]) }); // - 넣기
        Q.push({ idx + 1, total + (nums[idx + 1]) });      // + 넣기
    }
}
 
int solution(vector<int> numbers, int target) {
  
    BFS(numbers, target);
 
    return answer;
}