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

백준 23057 : 도전 숫자왕

 

문제 링크

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

23057번: 도전 숫자왕

 

 

문제 내용

오늘은 즐거운 축제날이다.

백남이는 축제에서 무엇을 할까 돌아다니던 중 도전 숫자왕이라는 행사를 발견했고 100만 원이라는 상금에 홀려 바로 참가하였다.

도전 숫자왕은 N개의 숫자 카드를 조합하여 다양한 수를 만드는 게임이다.

이번 라운드에서는 카드의 적힌 수의 합으로 만들 수 없는 수의 개수를 외치면 이긴다.

백남이가 1등을 하여 축제를 즐길 수 있도록 도와주자.

 

첫 번째 줄에는 카드의 개수 N(1≤N≤20)이 주어진다.

두 번째 줄에는 N$N$개의 수가 주어진다.

입력으로 주어지는 수는 100,000,000 이하의 자연수이다.

모든 카드에 적힌 수의 합을 M이라고 할 때, 1 이상 M이하의 자연수 중 만들 수 없는 수의 개수를 출력한다.

 

 

Idea

이 문제는 기본적으로브루트 포스 문제이기 때문에 원소 전체의 조합을 전부 검사해주면 된다.

 

[Code ver.1]

백트래킹 중 dfs 방식.

1) 원소를 탐색해가며 나오는 값들을 set에 넣어준다.

2) 최대 나올 수 있는 수에서 집합의 원소 개수를 빼준다.

 

[Code ver.2]

비트 마스크 방식.

1) 비트 마스크에 걸리는 원소들의 합을 set에 넣어준다.

2) 최대 나올 수 있는 수에서 집합의 원소 개수를 빼준다.

 

[Code ver.3]

약간 dp느낌의 방식.

1) 카드의 수를 입력받을 때마다 set에 있는 원소들과 합하여 임시로 vector에 저장해둔다.

2) vector에 저장된 수들은 다음 카드의 수를 입력받기 전 set에 저장하고 vector는 초기화한다.

3) 최대 나올 수 있는 수에서 집합의 원소 개수를 빼준다.

 

[시행착오]

초반엔 기본적으로 백트래킹중 dfs 방식을 선택하여 연산 도중 나오는 값을 계속 set에 값을 삽입하게끔 만들었다.

여기까진 괜찮았는데 결과 출력에서 문제가 생겼다. set은 자동정렬이기 때문에 들어있는 원소들을 검사해가면서 없는 수를 체크했는데 시간 초과가 걸렸다. (여기서 삽질 아닌 犬삽질....) 그냥 만들 수 있는 최댓값에서 set의 size를 빼주면 되는 거였는데 이 생각을 못해서 알고리즘을 바꾸기까지 했다...

그게 바로 비트 마스크(bitmask)를 이용한 방식. 그러나 앞서 원인과 마찬가지로 결과 출력을 저렇게 해버려서 시간 초과가 났다. 그러다 갑자기 size()를 사용하는 아이디어가 생각나서 바로 바꿔보니 "맞았습니다!!" 설마설마하면서 처음 짠 알고리즘에도 결과 출력을 바꿔봤더니 바로 통과... 킹받았다...

 

 

Code

[ ver.1 ]

#include <iostream>
#include <set>
#include <string.h>
using namespace std;
 
int card[21];
int N;
set<int> s;
 
void func(int idx, int sum)
{
    s.insert(sum);
 
    if (idx == N)
        return;
 
    func(idx + 1, sum + card[idx]);
    func(idx + 1, sum);
}
 
int main()
{
    int M, result;
 
    //init & input
    M = result = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &card[i]);
        M += card[i];
    }
 
    //backtracking
    func(0, 0);
 
    //result
    result = M - s.size() + 1;
    printf("%d\n", result);
    return (0);
}

 

 

[ ver.2 ]

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    int N, M, result;
    int card[21];
    set<int> s;
 
    //init & input
    M = result = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &card[i]);
        M += card[i];
    }
 
    //brute force & bit mask
    int select = 1, sum;
    while (1)
    {
        if (select == (1 << N)) break ;
        sum = 0;
        for (int idx = 0; idx < N; idx++)
        {
            if (select & (1 << idx))
                sum += card[idx];
        }
        s.insert(sum);
        select++;
    }
 
    //result & output
    result = M - s.size();
    printf("%d\n", result);
    return (0);
}

 

 

[ ver.3 ]

#include <iostream>
#include <set>
#include <vector>
using namespace std;
 
int main()
{
    int N, M, result;
    int card;
    set<int> s;
    vector<int> v;
 
    //input & algorithm
    M = result = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &card);
 
        M += card;
        v.push_back(card);
        for(int num : s)
            v.push_back(card + num);
        s.insert(v.begin(), v.end());
        v.clear();
    }
 
    //result & output
    result = M - s.size();
    printf("%d\n", result);
    return (0);
}