[C++] 백준 10448번 - 유레카 이론

---

0. 문제

 

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

1. 아이디어

 

1) 1000이하의 삼각수들만 들어있는 배열을 따로 하나 생성.

 

2) 완전 탐색을 통해 주어진 수가 3개의 삼각수들의 합으로 표현될 수 있는지 판단.

 

2. 소스코드

 

#include <iostream>
#include <memory.h>
int tri[1000];
bool triangleSum(int total)
{
    for (int p = 0; tri[p] != 0; p++)
    {
        for (int q = 0; tri[q] != 0; q++)
        {
            for (int r = 0; tri[r] != 0; r++)
            {
                int sum = tri[p] + tri[q] + tri[r];
                if (total == sum) return true;
            }
        }
    }
    return false;
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int T, index = 0;
    std::cin >> T;
    memset(tri, 0, sizeof(tri));
    for (int i = 1; (i * i + i) / 2 < 1000; i++)
    {
        int sum = (i * i + i) / 2;
        tri[index++] = sum;
    } // tri[0]부터 순서대로 1000 이하의 삼각수들을 배열에 입력
 
    for (int i = 0; i < T; i++)
    {
        int N;
        std::cin >> N;
        if (triangleSum(N)) std::cout << "1\n";
        else std::cout << "0\n";
    }
}

 

3. 결과

 

4. 피드백

 

• 벡터를 이용했다면 쓸데없는 메모리낭비를 막을 수 있었다.. 공부하자!

---

TO DO LIST: 벡터

---