[백준](2024) 유레카 이론 (설명/코드/정답)

 

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

 

 

난이도		알고리즘
	브론즈1	수학, 완전탐색

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 /  256MB

 

자연수 K가 3개의 삼각수의 합으로 표현될 수 있으면 1, 아니면 0을 출력하는 프로그램을 작성

삼각수 중복 가능

표준입력 사용

자연수 K (3<= K <= 1,000)

 

 

2. 설계/검증 

입력

- 테스트케이스 개수 

- 자연수 K

 

설계 

-  모든 삼각함수 생성 

-  삼각함수 합인지 

-  삼각함수로 표현될 수 있는 자연수인지 판정 

 

출력 

- 판단 O 이면 1 

- 판단 X 이면 0

시간 복잡도	최악의 경우	공간 복잡도
O(K^3)	85,184	O(1)

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // Scanner객체 생성
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스의 개수
        for (int i = 0; i < T; i++) { 
            int K = sc.nextInt(); 

            // 정수가 3개의 삼각함수의 합으로 표현될 수 있는지 여부를 확인 
            boolean isExpressible = isExpressibleAsTriangleNumber(K);
            // 결과 출력 
            if (isExpressible) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }

        // Scanner 객체 닫기
        sc.close();
    }


    // 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지를 판단하는 메소드
    private static boolean isExpressibleAsTriangleNumber(int K) {
        for (int i = 1; i <= K; i++) {
            int sum = i * (i + 1) / 2;
            for (int j = 1; j <= K; j++) {
                int sum2 = j * (j + 1) / 2;
                for (int k = 1; k <= K; k++) {
                    int sum3 = k * (k + 1) / 2;
                    if (sum + sum2 + sum3 == K) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}