백준 10448 - 유레카 이론

문제

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

10448번: 유레카 이론

 

풀이

K보다 작은 삼각수를 구해서 모두 구해서 합으로 표현가능한지 확인한다. 1000보다 작은 삼각수의 수는 생각보다 많지 않아서 가능하다.

 

1. K보다 작은 삼각수를 구한다

2. 3개씩 더하면서 합이 맞는지 확인한다.

 

코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int T;
    cin >> T;
 
    while (T--)
    {
        int K;
        cin >> K;
 
        vector<int> v;
        int i = 1;
        int plus = 2;
        while (i < K)
        {
            v.push_back(i);
            i += plus++;
        }
 
        i = 0;
        int j = 0, k = 0;
        int num1 = v[i], num2 = v[j], num3 = v[k];
        int result = 0;
 
        while (true)
        {
            if (num1 + num2 + num3 == K)
            {
                result = 1;
                break;
            }
 
            k++;
            if (k == v.size())
            {
                k = 0;
                j++;
                if (j == v.size())
                {
                    j = 0;
                    i++;
                    if (i == v.size()) 
                        break;
                }
            }
            num3 = v[k];
            num2 = v[j];
            num1 = v[i];
        }
 
        cout << result << '\n';
    }
 
 
    return 0;
}