[백준 10448 / JAVA] 유레카 이론

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

10448번: 유레카 이론

 

브루트 포스 문제를 풀 때마다 이렇게 푸는게 맞는지 확신이 들지 않는다.

더 좋은 풀이가 있을것 같으면서도 없는..게 문제인거 같다

 

그냥 무작정 모든 삼각수를 3번 더해서 입력한 값이 되는지 확인하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] s = new int[45];

    public static void main(String[] args) throws IOException {
        int N;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        int[] a = new int[N];

        //삼각수 입력
        for (int i = 0; i < 45; i++)
            s[i] = (i + 1) * (i + 2) / 2;

        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(br.readLine());
            
            //출력
            System.out.println(sol(a[i]));
        }

    }

    public static int sol(int n) {
        for (int i = 0; i < 45; i++) {
            for (int j = i; j < 45; j++) {
                for (int k = j; k < 45; k++) {
                    if (s[i] + s[j] + s[k] == n)
                        return 1;
                }
            }
        }
        return 0;
    }
}