9843. 촛불 이벤트 D5 (C++)

※ SW expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

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

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

 

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

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

 

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다.

 

#include <iostream>
#include <cmath>
 
using namespace std;
 
long long solve(long long n)
{
    long long temp = sqrt(n*2);
    if(temp*(temp + 1) / 2 == n)
        return temp;
    else
        return -1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n;
    int tc;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        cin>>n;
        cout<<'#'<<t<<' '<<solve(n)<<'\n';
    }
    return 0;
}

 

n(n+1)/2 공식을 이용해서 풀면 간단하게 풀 수 있다.

입력을 받은 숫자 n에 대해서 2를 곱하고 루트를 씌워준 다음, 소수점을 버린다.

그 수를 다시 n(n+1)/2에 대입해서 같으면 그 수를 리턴하고 다르면 -1을 리턴해서 출력하면 된다.