[코드포스 Practice16] A. Tanya and Toys

딱 보자마자 어떻게 풀지 감이 잡혔다. 

먼저 장난감을 정렬 한 다음

1부터 10^9까지 반복문 도는데 이미 가지고 있는 장난감이면 합에 포함 안 시킨다. 

그렇게 하다 합이 m을 넘으면 좋료~

 

당연히 10^9라서 long long으로 합을 구했다. 

 

코딩하면서 합이 long long을 벗어나면 어떡하지 이런 생각이 들었는데 1부터 n까지의 합이 n * (n -1) / 2니깐 10^9 * 10^9 = 10^18 / 2 라 long long 안에 있겠다 싶었다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n;
    i64 m, sum = 0;
    scanf("%d %lld", &n, &m);
    vector<int> v(n);
    vector<int> ans;
    
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    sort(v.begin(), v.end());
    int index = 0;
    for (int i = 1; i <= 1000000000; i++)
    {
        if(v[index] == i)
        {
            index++;
        }
        else
        {
            if (sum + i <= m)
            {
                sum += i;
                ans.push_back(i);
            }
            else
                break;
        }
    }
    
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << " ";
    }
    
    return 0;
}

 

 

 

---

 

 

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    set<int> has;
    
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        has.insert(x);
    }
    
    vector<int> ans;
    
    for (int i = 1; i <= m; i++)
    {
        if (has.find(i) != has.end())
            continue ;
            
        ans.push_back(i);
        m -= i;
    }
    
    printf("%d\n", ans.size());
    for (auto ai : ans)
        printf("%d ", ai);
    
    return (0);
}

 

이건 북님 코드

 

set이랑 find 쓴 거 보고 연습삼아 따라 쳤음. C++문법 아직 낯설어서 편하게 못 쓰겠다

 

암튼 set쓰면 따로 sort 안 해도 되고.. 찾는 건 find로 하구 신기