[C/C++] 백준 16564번 - 히오스 프로게이머

 

 

 

<코드>

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

long long X[1000001];
long long N, K, tmp, n, dif, ans;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> X[i];
	
	sort(X, X + N);

	

	while (true)
	{
		tmp = X[0]; // 현재 min값
		n = upper_bound(X, X + N, tmp) - X; // min값의 개수 (중복이 없다면 1)

		if (n == N) // 모든 원소의 값이 같을 경우 바로 답 출력
		{
			ans = tmp + K / n;
			break;
		}

		dif = X[n] - tmp; // 현재 min값과 다음 값과의 차이

		if (dif * n <= K)
		{
			X[0] += dif;
		}
		else
		{ // 
			ans = tmp + K / n;
			break;
		}

		K -= dif * n;

	}

	cout << ans << '\n';
}

 

풀이 방법

 

입력 예시

5 100
20 30 50 60 90

5(N)개의 캐릭터의 레벨은 20, 30, 50, 60, 90이고 (배열 X에 담겨있으며 이미 sorting된 상황) 100(K)만큼 레벨업을 할 수 있다. 답부터 말하자면 65이며 구하는 알고리즘을 설명하자면!

 

X[0]	X[1]	X[2]	X[3]	X[4]	남은 K값
20	30	50	60	90	100

 

먼저 tmp는 현재 배열에서의 min값이다. 예를들어 배열 값이 2 2 2 4 5 라면 tmp값은 2가 되는 것이다.

 

tmp = X[0]; // 현재 min값
n = upper_bound(X, X + N, tmp) - X; // min값의 개수 (중복이 없다면 1)

위의 코드에서 현재 min값과 같은 중복의 개수를 찾기 위해서 이분 탐색인 upper_bound 함수가 사용되었다.

upper_bound, lower_bound 의 설명 ( 출처 - https://cocoon1787.tistory.com/324 )

 

if (n == N) // 모든 원소의 값이 같을 경우 바로 답 출력
{
	ans = tmp + K / n;
	break;
}

dif = X[n] - tmp; // 현재 min값과 다음 값과의 차이

만약 배열 값이 10 10 10 10 10 이런식으로 될 경우 n은 5가 되고 X[n]에서 원소의 개수가 5개라서 마지막 인덱스가 4이기 때문에 오류가 발생한다. 따라서 그러한 예외를 처리하기 위해 (N==n) 일 때 while문을 탈출하도록 하였다.

 

if (dif * n <= K)
{
	X[0] += dif;
}
else
{
	ans = tmp + K / n;
	break;
}

K -= dif * n;

 

이 코드의 의미는 예를들어 현재 레벨 상황이 30 30 50 60 90이라고 할 때 min값의 개수인 n은 2, 그리고 min값과 다음 원소의 차이인 dif는 50-30인 20이다. 레벨이 30인 캐릭이 2개 있고 다음으로 레벨이 높은 캐릭은 50 레벨이므로 남아있는 K를 사용해서 30인 캐릭 두 개를 모두 50으로 맞출 수 있는가를 따진다.

레벨을 맞출 수 있다면 min은 50이 될것이고 K가 부족하다면 남아있는 K를 n개의 캐릭터에 N빵 해주면 된다.

 

 

 

www.acmicpc.net/problem/16564

16564번: 히오스 프로게이머