[백준 26123] 외계 침략자 윤이 (C++)

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

26123번: 외계 침략자 윤이

문제

---

외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 N개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 i번째 건물의 높이는 ℎ이다.

윤이는 울산을 파괴하기 위해 다음과 같은 계획을 세웠다. 윤이는 매일 UFO를 타고 울산의 상공을 가르며 가장 높이가 높은 빌딩에 레이저를 발사할 것이다. 레이저에 맞은 빌딩은 높이가 1 낮아진다. 만약 그 날에 가장 높이가 높은 빌딩이 여러 개라면, 해당하는 모든 빌딩에 레이저를 발사한다. 만약 이미 모든 빌딩의 높이가 0이 되었다면, 윤이는 더 이상 레이저를 발사하지 않는다.

윤이는 지금까지 D일 동안 계획을 착실하게 수행해 왔다. 윤이가 D일 동안 레이저를 발사한 총 횟수를 구하시오.

입력

---

첫 번째 줄에 건물의 개수 N과 윤이가 계획을 수행한 날의 수 D가 공백으로 구분되어 주어진다.

(1 ≤ N ≤ 300,000, 1 ≤ D ≤ 300,000)

두 번째 줄에 건물의 높이를 나타내는 N개의 정수 ℎ_i가 공백으로 구분되어 주어진다.

(1 ≤ ℎ_i ≤ 300,000)

출력

---

윤이가 D일 동안 레이저를 발사한 총 횟수를 출력한다. (32비트 정수 범위를 넘을 수 있음에 유의하라.)

 

 

문제 풀이

---

레이저를 발사할 때마다 1씩 높이가 낮아지므로 레이저를 발사하기 전 가장 높은 빌딩이 계속해서 레이저 발사의 타겟이 된다. 따라서 D일 동안 레이저 발사는 (레이저를 발사하기 전 가장 높은 빌딩의 높이) - (레이저를 발사하기 전 가장 높은 빌딩의 높이-1) - (레이저를 발사하기 전 가장 높은 빌딩의 높이 - 2)... 순으로 이루어진다.

D일 동안 해당 날짜에 레이저를 발사할 높이보다 크거나 같은 빌딩들을 모두 더하면 답이다. lower_bound를 이용해 해당 높이가 나오는 첫 index를 찾으면 N-index가 해당 날짜에 레이저를 쏜 횟수가 된다.

혹은 최종적으로 레이저를 다 발사한 후 가장 높은 빌딩의 높이는 H_i - D가 되므로 이 높이보다 큰 수에 대해 같거나 큰 빌딩들을 모두 반복적으로 더해주면 답이 된다.

 

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, D;
	long long answer = 0;
	cin >> N >> D;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	int currentHeight = arr[N - 1];
	if (currentHeight == 0)
	{
		cout << 0 << "\n";
	}
	else
	{
		for (int i = 0; i < D; i++)
		{
			int index = lower_bound(arr, arr + N, currentHeight) - arr;
			answer += N - index;
			currentHeight--;
			if (currentHeight == 0)
			{
				break;
			}
		}
		cout << answer << "\n";
	}
	return 0;
}