백준 10448 유레카 이론 (C++)

www.acmicpc.net/problem/10448

10448번: 유레카 이론

PS 관련 포스팅을 미루고 미루고 또 미루다가 드디어 처음 시작한다. 생각하고 있는 큰 트리가 있지만, 일단은 문제를 하나씩 올려가며 차근차근 정리하겠다.

 

문제에서 주어진 삼각수를 구하는 식으로부터 2차 방정식을 만들 수 있고,

그를 통해 주어진 입력값을 삼각수(Tn)라고 했을 때, 2차 방정식의 해 중에 양수만 취하면 그 삼각수를 만드는 n을 구할 수 있다.

그러면 모든 수를 검사할 필요 없이 n개만 확인하면 된다. 

 

caseDet는 재귀함수로써, 정확히 3번의 삼각수가 더해졌을 때, 입력값과 3개 삼각수의 합이 일치하는지 확인한다.

재귀 함수를 만드는 기본 방식대로 기저 조건을 확인하고, 해당되지 않으면 다음 재귀로 들어가는 방식이다.

가장 큰 입력값이 문제에서 주어지므로 사실 처음부터 삼각수를 다 구해놓은 배열을 갖고 시작할 수도 있다. 여기서는 그저 동적 할당을 연습하였다.

 

<주요 내용>

재귀함수, 동적 할당, 포인터 활용, 수학(2차 방정식)

 

<코드>

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

int input,c,sum;
int caseDet(int* arr);

int main()
{
    int* arrTN, bigTN,arrS, n,k=0;
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>input;
        bigTN=(int)(sqrt(8*input+1)-1)/2;
        arrTN=new int[bigTN+1]; 
        while(bigTN>0)
        {
            arrTN[k++]=bigTN*(bigTN+1)/2;
            bigTN--;
        }
        arrTN[k]=0;
        k=0;
        cout<<caseDet(arrTN)<<endl;
        c=0;
        sum=0;
        delete[] arrTN;
    }
    return 0;
}
int caseDet(int* arr)
{
    if (c==3)
    {
        if (sum==input) return 1;
        else return 0;
    }
    while(*arr)
    {
        sum+=*arr;
        c++;
        if (caseDet(arr)) return 1;
        else
        {
            sum-=*arr;
            c--;
            arr++;
            continue;
        }
    }
    return 0;
}