[SWEA] 9843번 : 촛불 이벤트

🔗 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR

✍️ 문제 풀이

해당 문제는 이진 탐색 문제로, 현재 양초 개수가 n개라고 할 때, (K * (K+1)) / 2 = n 을 만족하는 K(== 단의 수)의 값을 찾아야 한다.

1) 현재 가지고 있는 양초 개수 n을 입력 받는다.

2) 입력 받은 n으로 만들 수 있는 단의 수 K를 찾기 위한 이진탐색을 한다.

• start = 1, end = sqrt(2 * n)으로 초기화 한다.
  • K단에는 (K(K+1)) / 2 개의 양초가 필요하다. 따라서 (K(K+1)) / 2 = n
  • (K^2 + K) / 2 = n ➡️ (K^2+K) = 2n
  • K를 제외하고 생각하면 K^2 < 2N ➡️ K < sqrt(2n)
  • 따라서 end는 sqrt(2 * n)이 된다.

3) end가 start보다 작지 않을 때까지 아래 과정을 반복한다.

• start와 end의 중간 값으로 mid를 초기화 한다.
• 현재 단 수가 mid라고 할 때 필요한 양초 개수를 curLevel에 저장한다.
• n과 curLevel을 비교한다.
  • n > curLevel : 내가 가지고 있는 양초보다 더 적게 필요하므로 mid 위 값을 탐색한다. (start = mid + 1)
  • n == curLevel : 내가 가지고 있는 양초 개수와 딱 맞기 때문에 mid를 반환한다.
  • n < curLevel : 내가 가지고 있는 양초보다 더 많이 필요하므로 mid 아래 값을 탐색한다. (end = mid - 1)

4) start가 end보다 커질 때까지 mid를 반환하지 못했다면 n개의 양초로 삼각형을 만들 수 없는 경우이므로 -1을 반환한다.

❗ 해당 문제의 경우 테스트 케이스가 10만개인데, sync_with_stdio()와 cin.tie(), cout.tie()를 사용했음에도 불구하고 제한시간 초과가 발생했다. 이후 scanf()와 printf()로 변경하고 나서야 제한시간 내에 통과할 수 있었다. C와 C++ 사이 동기화를 끊으면 속도 차이가 거의 없는 것으로 아는데 왜 이런 결과가 나왔는지는 잘 모르겠다.. 코딩 테스트 문제를 풀 때는 가급적 scanf()와 printf()를 사용하는 습관을 들이는 것이 좋을 것 같다.. 라고 말했지만 cin, cout이 편한 걸 ㅠㅜ

🖥️ 풀이 코드

#include <iostream>
#include <cmath>

using namespace std;
long long n;

long long binary_search()
{
	long long start = 1, end = sqrt(2 * n), mid;		//  k단을 만들기 위해서는 k(k + 1) / 2 개의 양초가 필요 -> 초 개수를 n개라고 할 때, 단 개수 k는 sqrt(2 * n)보다 작다.

	while (end >= start)
	{
		mid = start + (end - start) / 2;
		long long curLevel = ((mid * (mid + 1)) / 2);
		if (n > curLevel)
			start = mid + 1;
		else if (n == curLevel)
			return mid;
		else
			end = mid - 1;
	}
	return -1;
}

int main()
{
	int t;
	scanf("%d", &t);

	for (int i = 0; i < t; i++)
	{
		n = 0;
		scanf("%lld", &n);
		printf("#%d %lld\n", i + 1, binary_search());
	}
	return 0;
}