[10448번] 유레카 이론

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 삼각수의 이해

2. 3중 포문과 시간 복잡도

삼각수는 다음 공식으로 모두 알아 낼 수 있다.

samgak[i] = i*(i + 1) / 2;

이제 알아내야 하는 것은, 이 삼각수를 3개를 이용하여 표현 할 수 있는 자연수를 구해야 한다.

결국 3중포문을 돌리면 끝이난다. 

이 문제는 계산기로 조금만 구해보면, 정확히 3개의 삼각수 합으로 이루어진 수이려면

k의 범위가 1000보다 작거나 같으니 결국 삼각수의 범위를 45까지 잡아주면 된다.

(1000보다 커지는 그때의 수)  참고로, 45 * 46 / 2 = 1035이다.

이렇게 되면 대개 코딩을 할 때, 3중포문에 대해 시간 복잡도를 생각해볼텐데 3중 포문에 대한 부담도 사라지게 되며

자연스럽게 코딩을  마무리 할 수 있다.(50 *50 * 50 = 125,000 이니 이것보다 작게 움직인다.)

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream>   using namespace std;   int samgak[51]; int ans[4000];   int main() {     for (int i = 1; i <= 45; i++)         samgak[i] = i*(i + 1) / 2;       for (int i = 1; i <= 45; i++)         for (int j = 1; j <= 45; j++)             for (int k = 1; k <= 45; k++)                 ans[ samgak[i] + samgak[j] + samgak[k] ] = 1;          int tCase, n;       cin >> tCase;       while (tCase--)     {         cin >> n;           if (ans[n] == 1)             cout << 1 << endl;         else             cout << 0 << endl;     }          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus