[C++]백준 - 23057번 문제

23057번: 도전 숫자왕 (acmicpc.net)

23057번: 도전 숫자왕

 

23057번 : 도전 숫자왕

---

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

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

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

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

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

 

입력

---

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

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

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

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

모든 숫자 조합을 담는 자료구조를 사용합니다.

 

다만, 중복은 배제하고 싶으니 Set을 사용할 것입니다.

 

Set은 값이 이미 존재하면 자동으로 배제합니다.

 

입력을 하나 하나 받을 때마다 기존 set에 담긴 원소를 더한 값을 새로 set에 담고, 입력을 담습니다.

 

예를 들어, 입력이 {1, 2, 4}일 경우,

 

- 1을 입력 받은 경우

Set의 상태 : { 1 }

 

- 2를 입력 받은 경우

Set의 상태 : { 1, 2, 3 } 

 

- 4를 입력 받은 경우

Set의 상태 : { 1, 2, 3, 4, 5, 6, 7 }

 

이제, M의 값을 구하고, 1~M까지의 수의 갯수는 M 개 이므로, 'M - Set에 담긴 숫자의 갯수'를 해주면 정답입니다.

 

코드

---

#include <iostream>
#include <set>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int M = 0;
    cin >> N;
    
    set<int> comb, temp;
    for(int i = 0; i < N; i++) 
    {
        int input;
        cin >> input;
        temp = comb;
        for(auto it = temp.begin(); it != temp.end(); it++) comb.insert(*it + input);
        comb.insert(input);
        M += input;
    }
    int result = M - comb.size();
    cout << result;
    return 0;
}

 

그 외

---

충남대학교 제 5회 생각하는 프로그래밍 대회 문제입니다.

제5회 생각하는 프로그래밍 대회 (acmicpc.net)

제5회 생각하는 프로그래밍 대회