[ SWEA 9843 ] 촛불 이벤트 (C++)

SWExpertAcademy의 촛불 이벤트(9843 / D5) 문제이다.

[ 문제풀이 ]

양초의 갯수를 이용해서 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구해야 하는 문제이다.

양초의 갯수가 어떤 특징을 갖는지 먼저 알아보자.

먼저, 양초가 1개 존재한다면 1단 촛불 삼각형을 만들 수 있다.

양초가 2개가 존재한다면 ?? 촛불 삼각형을 만들수가 없다.

양초가 3개가 존재한다면 ?? 2단 촛불 삼각형을 만들 수 있다.

.

위의 그림에서 삼각형 하나를 '양초' 라고 표현했을 때, 위의 그림과 같이 양초 3개로는 2단 촛불 삼각형을 만들 수 있다.

양초가 4개, 5개가 있다면 촛불 삼각형을 만들 수 없고, 양초가 6개가 있을 때는 다음과 같이 3단 촛불 삼각형을 만들 수가 있다.

.

그럼 여기서 양초의 갯수가 어떤 숫자일 때 촛불 삼각형이 되는지 안되는지 부터 알아보자. 몇 단인지는 그 후에 알아보자.

위에서 양초가 1개 ~ 6개인 경우를 한번 적어봤는데, 촛불 삼각형이 되는 경우는 [ 1 , 3 , 6 ] 개의 양초가 존재할 때만

가능했다.

그런데 ! 위의 [ 1 , 3 , 6 ] 숫자들의 공통점을 찾아보면 바로 "등차수열로 표현이 가능한 숫자" 라는 것이다.

1 = 1

3 = 1 + 2

6 = 1 + 2 + 3

위의 특징을 생각해보면, 아마 그 다음 4단 촛불 삼각형은 10개의 양초가 필요할 것이다.

10 = 1 + 2 + 3 + 4

우리에게는 양초의 갯수 N이 주어진다. 그리고 몇 단 촛불삼각형을 만들 수 있냐 라고 문제에서 물어봤는데, 우리가 구해야 하는 것은 다음과 같이 2가지가 있다.

1. 주어진 N이 등차수열로 표현이 가능한가 ?

2. 등차수열로 표현이 가능하다면, 이를 만족시키는 값이 얼마인가 ?

이렇게 2가지를 구하면 된다.

그럼 등차수열로 표현이 가능하다 라는 것은 무엇을 의미할까 ??

바로 a * (a + 1) / 2 = N 을 만족시키는 a값이 존재한다는 것을 의미한다. 이 때, a값을 우리에게 묻고 있는 것이다.

만약, 만족시키는 a값이 없다면 -1을 출력하면 되는 것이다.

그럼, a * (a + 1) / 2 = N 을 만족시키는 a 값을 찾아야 한다. 어떻게 찾아야할까 ??

먼저, 식을 대충 한번만 정리해보면, a * (a + 1) = N * 2 로 정리해볼 수 있다.

그럼, N * 2 = K 라고 바꿔보면, K = a * (a + 1)이 된다.

본인은 여기서 "수의 특징" 을 이용해서 접근해보았다.

K에 루트를 씌운 값을 작은 k로 표현해보자.

그럼 구하고자 하는 숫자 'K'는 k^2 <= K < (k + 1)^2 이라는 특징이 있다.

하나의 예를 들어보자. K = 5라고 가정해보면, 루트를 씌운 값인 k = 2.xxx 가 된다. 소수점은 떼고 정수만 구해보자.

그럼 k = 2가 된다.

2^2 <= 5 < (2 + 1)^2  == "4 <= 5 < 9" 가 성립하게 된다.

즉 ! 우리는 이 루트를 씌운 값을 통해서 a값을 구할 수가 있다.

1. K의 값(N * 2)에 루트를 씌운다.

2. 루트를 씌운 값에서, 소수점은 다 버리고 정수만 뽑아 온다. 이 때 나온 정수를 a라고 하겠다.

3. a * a + 1 = K 인지 확인 한다.

만약 3번에서 성립 한다면, 해당 a를 출력하면 되고, 성립이 하지 않는다면 -1을 출력하면 된다.

우리가 했던 숫자들을 예시로 한번 테스트를 해보자.

숫자 '6'은 3단 촛불삼각형을 만들 수 있었다.

그럼, 순서대로 진행해보자.

1. a * (a + 1) == 6 * 2 가 성립하는 a값을 찾아보자.

2. a * (a + 1) = 12 이고, 12에 루트를 씌워보자.

3. 12에 루트를 씌운값 = 3.xxx = 3

4. 3 * 4 = 12가 성립하는지 확인해보자.

5. 성립함으로 a = 3. 즉 ! 3단 촛불삼각형을 만들 수 있다.

그럼 8로 한번 진행해보자.

1. a * (a + 1) == 8 * 2 가 성립하는 a값을 찾아보자.

2. a * (a + 1) = 16 이고 , 16에 루트를 씌워보자.

3. 16에 루트를 씌운 값 = 4

4. 4 * 5 = 16 이 성립하는지 확인해보자.

5. 성립하지 않으므로, '8'이라는 숫자는 등차수열로 표현이 불가능하다는 것을 의미하고, 촛불 삼각형을 만들 수 없음을 의미한다.

위와 같은 특징으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <cmath>
 
#define endl "\n"
using namespace std;
 
long long N, Answer;
 
void Initialize() {}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    long long Candidate = sqrt(N * 2);
    if (Candidate * (Candidate + 1) == N * 2) Answer = Candidate;
    else Answer = -1;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}