[SW Expert Academy] 9843번 : 촛불 이벤트

[문제]

당신은 프로포즈를 위해 촛불을 삼각형으로 배치하고 있다. 촛불을 K단 크기로 배치하면, 1단에는 K개의 양초, 2단에는 K-1개의 양초, …, K단에는 1개의 양초를 배치해서 총 (K(K+1))/2개의 양초가 필요하다.

당신이 사용할 양초의 개수 N이 주어질 때, 이 양초를 모두 사용하면 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구하여라.

 

[입력]

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 양초 개수가 주어진다. (1≤N≤1018)

 

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다.

입력	출력
5 1 3 6 14 762078456028	#1 1 #2 2 #3 3 #4 -1 #5 1234567

 

[소스 코드]

 

#include <stdio.h>
#include <math.h>
int main(void)
{
	int test_case;
	int T;
	long long int candle = 0;
	double tri = 0;
	setbuf(stdout, NULL);
	scanf("%d", &T);
	for (test_case = 1; test_case <= T; ++test_case)
	{
		scanf("%lld", &candle);
		tri = (-1 + sqrt(1 + 8 * candle)) / 2;
		if (tri - (int)tri != 0) {
			tri = -1;
		}
		printf("#%d %.0lf\n", test_case, tri);
	}
	return 0; //정상종료시 반드시 0을 리턴해야 합니다.
}

[느낀 점]

10만개의 테스트 케이스를 1초 안에 통과해야하는데 math의 sqrt때문인지 제한시간 초과가 나왔다.

결국 촛불의 개수를 알고 있다면 몇단인지 확인하려면 K(K+1) = 2N을 풀어야하는데 K를 구하기 위해 근의 공식을 이용하니 루트를 씌워서 안되는 것 같다.

다른 방법이 있는지 확인해보면 좋겠다.

[링크]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR&categoryId=AXGBKzuaPOoDFAXR&categoryType=CODE