1568 새

 

새의 수가 10^9라 어떻게 하지 고민.. 고민하다가 숫자의 누적 합을 사용하면 되겠다 싶었고 또 그걸 나열해보니 뭔가 이진수 계산 같았다. 

 

십진수 17을 이진수로 만드려면 17에서 16빼고 1빼면 되니깐 10001이 된다. 그것처럼 14를 구하기 위해서 10을 빼고 3을 빼고 1을 뺴면 되지 않을까..

 

그래서 먼저 누적합을 저장하는 배열을 만들고 그 다음에 가장 큰 수 부터 빼기 시작했다. 그런데 문제는 5 같은 경우는 3, 1, 1 이렇게 1을 두 번 빼야한다. 그래서 숫자를 한 번 빼고 나서 다시 한 번 더 체크할 수 있게 했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    i64 n;
    scanf("%lld\n", &n);
    
    vector<i64> v(50000);
    i64 count;
    for (int i = 1; v[i - 1] <= 1000000000; i++)
    {
        v[i] = i + v[i - 1];
        count = i;
    }
    
    int res = 0;
    for (int i = count - 1; n != 0; i--)
    {
        if (n < v[i])
            continue;
        n -= v[i];
        res += i;
        i++;
    }
    
    printf("%d\n", res);
    
    return 0;
}