백준 10448번 : 유레카 이론(C 언어)

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

Code:

#include <stdio.h>
 
int main()
{
    int x = 0;
    scanf("%d", &x);
    int i, j, k;
    int arr[45] = { 0, };
    int check = 0;
    int sum = 0;
    int flag = 0;
    for (i = 1; i < 45; i++)
    {
        arr[i] = (i * (i + 1))/2 ;
    }
    while (x--)
    {
        flag = 0;
        sum = 0;
        scanf("%d", &check);
        for (k = 1; k < 45; k++)
        {
            for (j = 1; j < 45; j++)
            {
                for (i = 1; i < 45; i++)
                {
                    sum = arr[i] + arr[j] + arr[k];
                    if (sum == check)
                    {
                        flag = 1;
                        printf("1\n");
                        break;
                    }
                    if (sum > check)
                    {
                        break;
                    }
                }
                if (flag == 1)
                {
                    break;
                }
            }
            if (flag == 1)
            {
                break;
            }
        }
        if (flag == 0)
        {
            printf("0\n");
        }
    }
}

문제풀이:

우선 삼각수들을 먼저 구해서 arr배열에 넣어준다. 테스트가 1000이하이므로 n은 45가 제한임을 알 수 있다.

그 뒤 3개의 변수 i, j, k 를 이용해서 3개의 삼각수를 이용해 값을 만들 수 있는지 확인해 보았다.