[프로그래머스 Level 1] 두 개 뽑아서 더하기

문제

두 개 뽑아서 더하기  

 

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

1. numbers의 길이는 2 이상 100 이하입니다.
2. numbers의 모든 수는 0 이상 100 이하입니다.

 

코드

#include <vector>
#include <set>

using namespace std;

set<int> s;

void DFS(int now, int pos, int sum, vector<int> numbers)
{
    if(now == 2)
    {
        s.insert(sum);
        return;
    }
    
    for(int i = pos; i < numbers.size(); i++)
        DFS(now + 1, i + 1, sum + numbers[i], numbers);
}

vector<int> solution(vector<int> numbers) 
{
    DFS(0, 0, 0, numbers);
    
    vector<int> answer(s.begin(), s.end());
    
    return answer;
}

 

나의 생각

DFS, BFS를 너무 좋아한 나머지 문제를 DFS로 풀어버렸다.

 

배열에서 두 개를 뽑는 문제로 DFS가 아닌 중첩 for문으로도 조합을 구할 수 있다.  DFS나 이중 for문 둘 다 기저에 깔린 개념은 동일하니 말이다. 다만 문제를 조금 변형해서 다섯 개를 뽑아 더해 만들 수 있는 모든 수를 구하라면 다섯 번의 중첩 for문을 작성해야 하나 DFS로 푸는 방법이 더 쉬울 것이다.