[BOJ] 백준 10448 유레카 이론

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

Approach

완전탐색 유형 문제이다.

 

입력받는 K의 범위가 (3 ≤ K ≤ 1,000) 이기 때문에

삼각수로 구성한다면 1000 이하의 숫자 3개로 구성해야 한다.

그 이상의 수치는 의미가 없는 것이다.

- 44번째 값 = 990

- 45번째 값 = 1035

 

삼각수는 문제에서 주어진 공식으로 구할 수 있다.

void makeTriangle()
{
    for (int i = 1; i <= MAX_TRI; i++)
    {
        triangle[i] = i * (i + 1) / 2;
    }
}

 

K의 범위를 고려한다면 때문에 1~45번째까지 값들을 배열에 저장하면 된다.

배열 원소 3개로 만들 수 있는 숫자를 별도의 배열 ans[]에 처리할 수 있다.

→ 3중 for문

→ 50 *50 * 50 = 125,000로 제한시간 1초내로 구해진다.

▶ [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기  

[알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기

 

ans[] 배열 크기는 삼각수의 최대값이 3번 더해지는 것보다 크게 설정하면 되는데

→1035 + 1035 + 1035 < 5000 정도로 잡아서 처리.

K 한개를 입력받고 3개의 삼각수로 구성가능한지 확인하는 것보다.

삼각수 3개로 만들 수 있는 숫자를 미리 구해놓는 것이다.

---

#include <iostream>

using namespace std;

const int MAX_TRI = 45 + 2;
const int MAX_K = 5e3 + 2;
int triangle[MAX_TRI];
bool ans[MAX_K];
int TC, K;

void makeTriangle()
{
    for (int i = 1; i <= MAX_TRI; i++)
    {
        triangle[i] = i * (i + 1) / 2;
    }
}

void checkEureka()
{
    for (int i = 1; i <= MAX_TRI; i++)
        for (int j = 1; j <= MAX_TRI; j++)
            for (int k = 1; k <= MAX_TRI; k++)
                ans[triangle[i] + triangle[j] + triangle[k]] = true;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    makeTriangle();
    checkEureka();
    scanf("%d", &TC);
    while (TC--)
    {
        scanf("%d", &K);
        printf("%d\n", ans[K] ? 1 : 0);
    }
}