[백준/C++] 급상승 (No. 23978)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 상승시켜야하는 코인 가격의 최소를 구하는 문제다.

 

그러므로 코인의 가격을 C라고 하면 가격이 C일 때 현금화 했을 때 가격이 K보다 크거나 같게 할 수 있는지 판단하면 된다.

 

이때, 적절한 C를 빠르게 찾기 위해 이분탐색을 사용하면 O(N*log K)로 문제를 해결할 수 있다.

 

그러므로 범위를 최소 범위와 최대 범위인 st=1, ed=2*10^9로 설정하고 이분탐색을 이용해 적절한 C가격을 찾아나가면 된다.

 

이때, 코인의 상승가격이 C인 경우 현금화 가격 K가 가능한지 계산하기 위해서는 상승 가격의 기간이 중요하다.

 

코인이 상승하는 기간의 차이를 A일이라고 하면, 상승가격 C와 A를 비교한다.

그리고 A가 C보다 크다면 그 사이에 현금화 해서 얻는 돈은 C*(C-1)/2이다.

만약 C가 A보다 크다면, A일 후에는 다시 코인가격이 C가 되므로 C*(C-1)/2 - (C-A)*(C-A-1)/2 만큼 돈이 현금화 된다.

 

이를 이용해 현금화한 돈이 K가 되는지 구하고 이분탐색으로 빠르게 계산하면 된다.

 

 

[아이디어 정리]

1. 이분 탐색을 이용해 코인의 가격이 C일 때 현금화 한 가격을 계산해 K와 비교한다. 
2. 이때, 현금화 한 가격을 구하기 위해서는 상승하는 날의 기간을 비교해 계산한다.
3. 기간의 차이가 A라면 A와 C를 비교하고 A가 크면 C*(C-1)/2를 더한다.
4. A와 C를 비교했을 때, C가 더 크다면 C*(C-1)/2 - (C-A)*(C-A-1)/2를 더한다.
5. 최종적으로 구한 C를 출력한다.

 

 

Code

 

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

long long calc(long long n, long long m)// 누적 N일 합
{
	long long ans = n * (n - 1) / 2;
	ans -= m * (m - 1) / 2;
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long N,K;
	cin >> N >> K;
	vector<long long> v(N);
	for (int i=0; i<N; i++)
	{
		cin >> v[i];
	}
	long long st = 1, ed = 2000000001;
	long long mid = 0;
	while(st<=ed)
	{
		long long ans = 0;
		mid = (st + ed) / 2;
		bool flag = false;
		for(int i=0; i<N-1; i++)
		{
			ans += calc(mid, mid-min(mid, v[i+1]-v[i]));
			if (ans>=K)
			{
				flag = true;
				ed = mid - 1;
				break;
			}
		}
		if (!flag)
		{
			ans += calc(mid, 0);
			if (ans>=K)
			{
				ed = mid - 1;
			}
			else
			{
				st = mid + 1;
			}
		}
	}
	cout << ed;
	return 0;
}

---

 

이러한 문제의 유형이 많아서 이분탐색을 떠올리면 쉽게 풀 수 있는 문제였다.

단지 다른 점이 있다면, 현금화 가격을 구하기 위해서 기간을 이용해야하는 점과 C++의 경우 long long의 범위를 벗어나 답에 오류가 생기지 않도록 조심해야 한다는 점이 있었다.

 

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