[백준 27724] 팝핀 소다 (C++)

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

문제

---

민겸이는 shake! 2022를 맞아 레크리에이션 행사를 기획하였다. 이 행사의 메인 컨텐츠는 탄산이 매우 강력해서 마시기 힘든 팝핀 소다를 빨리 마시는 대회이다. 이 대회는 아래와 같이 진행된다.

• 대회에는 총 𝑁(단, 𝑁은 2의 거듭제곱수)명의 선수가 참가한다.
•  𝑁명의 선수들은 양의 정수로 표현 가능한 탄산 내성을 가지고 있다. 각 선수의 탄산 내성은 1 이상 𝑁 이하이며, 각 선수의 탄산 내성은 중복되지 않는다.
•  𝑁명의 선수들은 다른 선수와 두 명씩 짝지어 빨리 마시기 대결을 한다. 이 과정에서 총 𝑁/2번의 대결이 진행된다. 각 대결의 패자 𝑁/2명은 대회에서 나가고, 승자 𝑁/2명은 동일한 방식으로 두 명씩 짝지어 대결한다. 승자가 한 명 남을 때까지 이 과정을 반복한다.
• 각 대결에서는 탄산 내성이 높은 사람이 승리하고 낮은 사람이 패배한다.
• 하지만, 이변이 일어나면 승부 결과가 바뀐다. 이변이 일어날 경우 탄산 내성이 높은 사람이 패배하고 낮은 사람이 승리한다.

시은이는 이 대회의 참가자이다. 이 대회에서 일어날 수 있는 총 이변의 수와 시은이의 탄산 내성이 주어질 때, 시은이가 이 대회에서 승리할 수 있는 대결이 최대 몇 회인지 구하라.

 

입력

---

입력의 첫 번째 줄에 대회에 참가하는 선수의 수 𝑁, 일어날 수 있는 이변의 수 𝑀, 시은이의 탄산 내성 𝐾가 공백으로 구분되어 주어진다. 주어지는 모든 수는 정수이다. (2 ≤ 𝑁 ≤ 262144, 0 ≤ 𝑀 ≤ 𝑁, 1 ≤ 𝐾 ≤ 𝑁)

 

출력

---

대회에서 시은이가 승리할 수 있는 총 대결의 수를 출력한다.

 

문제 풀이

---

수학을 이용한 문제.

이변이 일어날 수 없을 때 이길 수 있는 최대값을 구한 후 이변의 수 M을 더하면 이길 수 있는 총 대결 수를 구할 수 있다. 단, 한 사람이 할 수 있는 최대 대결 수는 log2(N)이므로, 이보다 작은지 확인한다.

 

아래는 코드.

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

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

	int N, M, K;
	int answer = 0;
	cin >> N >> M >> K;
	while (K != 1)
	{
		if (K % 2 == 1)
		{
			K--;
		}
		K /= 2;
		answer++;
	}
	answer += M;
	int maxCount = log2(N);
	answer = min(answer, maxCount);
	cout << answer << "\n";
	return 0;
}