BOJ 23978 C++

문제접근

예제에서 살펴볼 수 있듯이 1 2 4가 주어졌을때

3,3,2,3,2,1,0

이렇게 순차적으로 줄어드는 값이라는걸 알 수 있다. 오름차순으로 주어지긴때문에 각 구간의 차이를 (날짜)

arr[i] - arr[i - 1]

이렇게 나타낼 수 있다. 그렇다면 날짜의 차이를 이용하여 코인의 가격을 보면

ll fac(ll now, ll next,ll z)
{
    ll sum = 0;
    ll st = abs(next - now);
    for (int i = 0; i < st; i++)
    {
        sum += z;
        if (z == 0)
            break;
        
    }
    return sum;
}

하지만 이렇게 하면 시간초과가 난다. 그래서 1부터 n까지의 합을 구하는 수학식을 사용한다.

1부터 n까지의 합 식: (n * (n + 1)) / 2 10일때 10 * 11 / 2 이므로 55가 나오게 된다.

그렇다면 10의 값이 코인가격으로 주워졌을때 1일에서 5일까지는 10 9 8 7이므로 34가 될것이다. 이를 수학식으로 나타내면

(10 * (5 - 1) - ((5 - 1) * ((5 - 1) - 1) / 2))

계산해보면 40 - ((4 * 3) / 2) 이므로 34가 나오게 된다.
이렇게 n부터 n - a까지의 합을 구할 수 있다.
이를 이용하여 시간초과가 나지 않게 풀 수 있다.

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;

ll cal(ll w, ll mid)
{
	ll sum = (mid * w) - (w * (w - 1) / 2);
	return sum;
}

ll sol(const vector<ll>& x,ll mid)
{
	ll sum = 0;
	int size = x.size();
	for (int i = 1; i < size; i++)
	{
		sum += cal(min(x[i] - x[i - 1], mid), mid);
	}
	sum += cal(mid, mid);
	return sum;
}

ll ebun(const vector<ll>& x, ll k)
{
	ll lo = 1;
	ll hi = 1500000000; //구간설정 주의
	while (lo <= hi)
	{
		ll mid = (lo + hi) / 2;
		if (sol(x, mid) < k)
		{
			lo = mid + 1;
		}
		else
		{
			hi = mid - 1;
		}
	}
	return lo;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	ll k;
	cin >> n >> k;
	vector<ll> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	cout << ebun(v, k);
}

시간초과 코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;

ll fac(ll now, ll next,ll z)
{
    ll sum = 0;
    ll st = abs(next - now);
    for (int i = 0; i < st; i++) //이부분에서 시간초과가 난다
    {
        sum += z; 
        if (z == 0)
            break;
        
    }
    return sum;
}

ll cal(const vector<ll>& x,ll mid)
{
    ll sum = 0;
    int size = x.size();
    for (int i = 1; i < size; i++)
    {
        sum += fac(x[i - 1], x[i],mid);
    }
    sum += fac(x[size - 1], 0, mid);
    return sum;
}

ll ebun(const vector<ll>& x, ll k)
{
    ll lo = 1;
    ll hi = k;
    while (lo <= hi)
    {
        ll mid = (lo + hi) / 2;
        if (cal(x, mid) < k)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return lo;
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    cout << ebun(v, k);
}