BOJ 10448 - 유레카 이론 / C++

문제 링크 : https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

 

 

풀이

자연수 k의 범위는 1000까지이고 삼각수의 공식은 n * (n + 1) / 2 이므로

44 * 45 / 2 = 990, 탐색 범위는 n = 44까지 하면 된다.

 

삼각수를 저장하는 vector를 하나 생성하여 1부터 44까지의 n * (n + 1) / 2 를 원소로 넣는다.

3중 반복문으로 삼각수들을 더하며 n을 만들 수 있는지 체크하는 함수도 생성해준다.

n을 만들 수 있다면 바로 1을 return하고 3중 반복문을 벗어나면 만들 수 없는 것이므로 0을 return한다.

이제 테스트케이스마다 앞에서 생성한 함수로 체크하여 출력해주면 된다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> triNums;

int checkAns(int n) {
    for (int i : triNums) {
        for (int j : triNums) {
            for (int k : triNums) {
                if (i + j + k == n)
                    return 1;
            }
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    for (int i = 1; i < 45; i++) {
        triNums.push_back(i * (i + 1) / 2);
    }

    int t; // test case
    cin >> t;

    while(t-- > 0) {
        int n;
        cin >> n;
        cout << checkAns(n) << '\n';
    }
}