[코딩 테스트 문제 풀이 시리즈] 10448번 - 유레카 이론: 삼각수 완전 탐색

문제 개요

오늘은 백준 10448번 “유레카 이론” 문제를 풀어보았다.

이 문제는 완전 탐색의 정석을 보여주는 대표적인 예시로, 세 개의 삼각수의 합으로 어떤 수가 표현되는지 확인하는 문제다.

문제를 처음 접했을 때는 “삼각수? 세 개의 수?”라는 막막함이 들 수 있지만, 사실은 브루트포스로 무식하게 전부 확인하면 되는 문제다.

---

문제 설명

삼각수(Triangle Number)란?
1부터 n까지의 합을 뜻하며, 공식은 다음과 같다.
T(n) = n × (n + 1) / 2

 

예를 들어,

• T(1) = 1
• T(2) = 3
• T(3) = 6
• T(4) = 10
• …

이런 삼각수 중에서, 어떤 자연수 K가

T(i) + T(j) + T(k) 형태로 표현될 수 있다면, 이 수는 유레카 수라고 부른다.

 

---

문제 접근 방식

 

문제에서 주어진 조건을 보면 K는 최대 1000 이하의 자연수이다.

삼각수는 T(n) = n(n+1)/2이기 때문에, T(44) = 990로 1000을 넘기지 않는 가장 큰 삼각수는 T(44)임을 알 수 있다.

즉, 가능한 삼각수는 T(1)부터 T(44)까지 총 44개뿐이다.

 

이 말은 곧, 세 개를 중복 포함하여 골라서 더해도 가능한 조합이 44^3 = 85,184개 정도라는 뜻이며,

이는 충분히 **완전 탐색(Brute Force)**으로 커버 가능한 범위다.

---

핵심 풀이 전략

1. 삼각수 목록을 미리 구한다
   • 1부터 44까지 삼각수를 모두 배열에 저장해둔다.
2. 세 개의 삼각수를 중복 포함하여 모두 더해본다
   • 3중 for문을 통해 T[i] + T[j] + T[k] == K 인 경우가 존재하는지 확인한다.
3. 존재 여부를 출력
   • 조건을 만족하는 조합이 하나라도 존재하면 1, 없으면 0을 출력한다.

---

코드 예시 (Java)

 

import java.util.*;

public class Main {
    static List<Integer> triangleNumbers = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        generateTriangleNumbers();

        while (T-- > 0) {
            int k = sc.nextInt();
            System.out.println(isEureka(k) ? 1 : 0);
        }
    }

    private static void generateTriangleNumbers() {
        for (int i = 1; i <= 44; i++) {
            triangleNumbers.add(i * (i + 1) / 2);
        }
    }

    private static boolean isEureka(int k) {
        for (int i = 0; i < triangleNumbers.size(); i++) {
            for (int j = 0; j < triangleNumbers.size(); j++) {
                for (int m = 0; m < triangleNumbers.size(); m++) {
                    int sum = triangleNumbers.get(i) + triangleNumbers.get(j) + triangleNumbers.get(m);
                    if (sum == k) return true;
                }
            }
        }
        return false;
    }
}

 

여기서 배운 점

• 완전 탐색은 가능한 조합의 개수만 제한적이라면 충분히 사용 가능한 강력한 무기다.
• 사전 계산 (삼각수 리스트 만들기)을 통해 중복 계산을 줄이는 습관이 중요하다.
• 문제를 접했을 때, 일단 조건을 수치화해서 계산해보는 습관이 필요하다.
• “44^3 정도면 충분히 가능한 수준이겠네?” 같은 판단.