[백준 29717] 슬라임 잡고 레벨 업! (C++)

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

문제

---

오늘은 많은 사람이 기대하던 《실브 스토리》게임이 출시되는 날이다!

《실브 스토리》는 MMORPG 장르 게임으로, 몬스터를 잡아 경험치를 모으고 레벨 업을 할 수 있으며, 레벨 업에 필요한 경험치를 넘을 때마다 그에 필요한 경험치만 소진하고 남은 경험치를 그대로 보유한다. 하지만 일반 게임들과 다르게 특이한 점이 두 가지 있다.

첫 번째는 게임에 존재하는 몬스터가 슬라임뿐이라는 것이다. 슬라임을 처치했을 때 주는 경험치 또한 특이한데, 유저가 지금까지 처치한 슬라임 수를 𝑥라 할 때, 새로운 슬라임을 처치하면 𝑥+1 만큼의 경험치를 얻게 된다.

두 번째는 레벨 업에 필요한 경험치의 증가 방식이다. 현재 레벨에서 레벨 업에 필요한 경험치가 𝑦라 하면 레벨 업 시 경험치 𝑦를 소모한 뒤 다음 레벨 업에 필요한 경험치는 𝑦+2가 된다. 레벨 1일 경우 레벨 업 필요한 경험치는 2이다.

《실브 스토리》에 처음 접속하는 신규 유저는 레벨 1, 경험치 0으로 시작한다. 당연히 처치한 슬라임의 수도 0이다.

신규 유저 브실이는 지금부터 슬라임을 𝑁마리 처치할 경우 자신이 레벨 몇이 될지 궁금해졌다. 슬라임을 잡을 계획을 철저하게 세우느라 바쁜 브실이를 위해 우리가 대신 브실이의 레벨이 몇이 될지 계산해 주자!

 

입력

---

 

첫 번째 줄에 테스트 케이스의 수 𝑇가 주어진다. (1 ≤ 𝑇 ≤ 1000)

두 번째 줄부터 𝑇+1번째 줄까지, 줄마다 정수 𝑁이 주어진다. (1 ≤ 𝑁 ≤ 10⁹)

 

출력

---

각 테스트 케이스마다, 슬라임을 𝑁마리 처치 후 브실이의 레벨이 얼마나 될지를 한 줄에 하나씩 출력한다.

 

문제 풀이

---

수학 + 이분탐색문제.

슬라임은 한 마리 잡을 때마다 슬라임으로부터 얻을 수 있는 경험치가 1경험치씩 획득하므로 N마리를 잡았을 때 얻을 수 있는 경험치는 1+2+3+...+N이다. 이는 등차수열의 합 공식에 의해 총 N*(N+1)/2 경험치만큼을 얻게 된다.

특정 레벨의 레벨 업에 필요한 경험치는 1레벨은 2, 2레벨은 4, 3레벨은 6, 4레벨은 8,로 마찬가지로 등차 수열의 형태이다. 따라서 특정 레벨의 레벨 업에 필요한 경험치는 N*(N+1)이다.

이제 이분 탐색을 통해 레벨을 정하고 해당 레벨이 N마리의 슬라임을 잡아서 얻을 수 있는 레벨인지 확인한다.

만약 특정 레벨(mid)까지의 레벨 업에 필요한 경험치가 슬라임을 잡아서 얻을 수 있는 경험치보다 작다면, right를 mid-1로 변경하여 범위를 줄여 탐색한다.

특정 레벨(mid)까지의 레벨 업에 필요한 경험치가 슬라임을 잡아서 얻을 수 있는 경험치보다 크거나 같다면, mid 레벨은 넘을 수 있다. 두 경험치가 같다면 mid레벨에서 레벨 업 하여 mid+1 레벨이 된다.

 

int 타입 오버플로우에 주의.

 

아래는 코드.

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

int main()
{
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		long long N;
		cin >> N;
		long long slimeEXP = ((N + 1) * N) / 2;
		long long left = 1;
		long long right = 1000000000;
		long long answer = 1;
		while (left <= right)
		{
			long long level = (left + right) / 2;
			long long needEXP = (level + 1) * level;
			if (needEXP < slimeEXP)
			{
				left = level + 1;
				answer = max(level + 1, answer);
			}
			else if (needEXP > slimeEXP)
			{
				right = level - 1;
			}
			else
			{
				answer = level + 1;
				break;
			}
		}
		cout << answer << "\n";
	}
	return 0;
}