백준 10448

 

배워두면 쓰기 좋은 개념이 나와서 써본다.

배열로 어떠한 조건이 맞는지 아닌지 확인할 때는 이렇게 boolean의 배열을 만드는 게 좋다.

이런 배열을 여러번 쓸 때는 이런 조건을 한번만 정의해두면 되기 때문에 시간복잡도에서 굉장히 유리하다.

 

아이디어는 다음과 같다.

삼각수 두개를 합한 배열 + 삼각수를 합한 배열 == 삼각수 세개를 합한 배열

 

1. 삼각수 두개를 합한 boolean의 배열을 만든다.

2. .삼각수 세개를 합한 boolean의 배열을 만든다.

3. 입력된 수의 index가 tripleOfEuraka에 속하는지 확인한다. (배열 인덱스가 입력된 수이고, 그에 대한 true, false로 알 수 있다.)

 

package programers;

import java.util.Scanner;

public class EurekaTheory {


    boolean[] isSumOfEureka = new boolean[1001];
    boolean[] isTripleOfEureka = new boolean[1001];


    public void processSumOfEureka() {
        for (int i = 1; i < 45; i++) {
            for(int j = 1; j < 45; j++) {
                int eureka1 = i*(i+1)/2;
                int eureka2 = j*(j+1)/2;
                if (eureka1 + eureka2 < 1000 && !isSumOfEureka[eureka1+eureka2]) {
                    isSumOfEureka[(i*(i+1)/2) + (j*(j+1)/2)] = true;
                }
            }
        }
    }

    public  void processTribleOfEureka() {
        for (int i = 1; i < 1000; i++) {
            if (isSumOfEureka[i]) {
                for (int j = 1; j < 45; j++) {
                    int eureka = j*(j+1)/2;
                    if(i+eureka > 1000) {
                        break;
                    }
                    isTripleOfEureka[i+eureka] = true;
                }
            }
        }
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        EurekaTheory main = new EurekaTheory();
        main.processSumOfEureka();
        main.processTribleOfEureka();
        int num = sc.nextInt();
        for(int i= 0; i < num; i++) {
        System.out.println(main.isTripleOfEureka[sc.nextInt()]? 1: 0);
        }
    }
}