[BOJ 10448] 유레카 이론

어떤 수가, 최대 3개 중복 허용인 삼각수의 합으로 표현되는지 알아봐야 한다.

 

 

 

그러기 위해서는, 전체 탐색을 하거나 삼각수의 합으로 표현되는지 확인하는 신기한 방법을 찾아야 하는데...

 

 

 

이 문제의 경우, 자연수의 범위가 1000까지 이므로, 전체 탐색을 해도 시간복잡도가 크지 않다.

 

 

 

전체탐색으로 문제를 풀기로 결정하면, 삼각수의 합이 1000이하인 값들을 구해놓고,

 

 

 

3중포문을 통해서, 만들 수 있는 값들을 모두 체크하면 된다.

 

 

 

해설코드(C++).

 

 

#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
 
int T;
int K;
int a[1001];
vector<int> v;
 
int main() {
    int sum = 1;
    int idx = 1;
 
    memset(a, 0, sizeof(a));
    while(sum <= 1000){
        v.push_back(sum);
        idx += 1;
        sum += idx;
    }
    
    for(int i = 0; i < v.size(); i++){
        for(int j = i; j < v.size(); j++){
            for(int k = j; k < v.size(); k++){
                if(v[i] + v[j] + v[k] <= 1000)
                    a[v[i] + v[j] + v[k]] = 1;
            }
        }
    }
    
    cin >> T;
    for(int i = 1; i <= T; i++){
        cin >> K;
        cout << a[K] << endl;
    }
    return 0;
}