[백준] 23057번 : 도전 숫자왕 - C++

문제

https://www.acmicpc.net/problem/23057

23057번: 도전 숫자왕

---

설명

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int card[21];
vector<int> vec;
int sum=0;
int N;

void DFS(int i, int num)
{
    vec.push_back(num);
    if(i == N) return;
    
    DFS(i+1,num+card[i+1]);
    DFS(i+1,num);
}

int main()
{
    cin>>N;
    
    for(int i = 0;i<N;i++)
    {
        cin >> card[i];
        sum += card[i];
    }
    for(int i = 0;i<N;i++)
    {
        DFS(i, card[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    
    cout<<sum - vec.size();
}

 

이 문제에서는 우선, 입력받은 숫자카드로 만들 수 있는 숫자들을 구해야한다.

만들 수 있는 숫자의 개수는 DFS를 통해서 구했다.

첫번째 카드부터 DFS함수의 인자로 넣어주어 만들 수 있는 숫자들을 벡터 vec에 삽입해준다.

재귀 호출을 통해서, 다음 카드를 사용하는 경우와 다음 카드를 사용하지 않는 경우를 구해주었다.

erase와 unique를 사용하여 중복원소를 제거해준다.

카드의 합에서 vec사이즈를 빼면 원하는 출력값이 나온다.