[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)10448번, 유레카 이론

문제 링크

10448번: 유레카 이론

---

 

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 모든 자연수는 최대 3개의 삼각수의 합으로 표현할 수 있습니다.

2. T개의 자연수 K가 3개의 삼각수의 합으로 표현할 수 있는지에 따라 결과를 출력합니다.

3. 3개의 삼각수는 모두 달라야할 필요는 없다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 1~1000까지 3개의 삼각수의 합으로 표현할 수 있는지 탐색합니다.

 

3. T개의 자연수를 3개의 삼각수의 합으로 표현 가능한지에 따라 결과를 출력합니다.

 

 

3개의 삼각수의 합으로 표현 가능한지 탐색

 

1 ~ 1000까지 3개의 삼각수의 합으로 표현 가능한지 탐색합니다.

 

1000까지 표현할 수 있는 삼각수의 최대값 : 44

 

(44 × 45) ÷ 2 = 990

 

1 ~ 44까지의 삼각수를 먼저 구한뒤 탐색을 진행합니다.

 

삼각수 1 : 1

삼각수 2 : 3

...

삼각수 44 : 990

 

1 ~ 1000까지 3개의 삼각수의 합으로 표현 가능한지 탐색

 

1 : 1

2 : 1 + 1

3 : 1 + 1 + 1

4 : 1 + 3

5 : 3 + 1 + 1

6 : 3 + 3

7 : 3 + 3 + 1

....

1000 : 861 + 136 + 3

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

T = 3개

 

K

10

20

1000

 

2. 1~1000까지 3개의 삼각수의 합으로 표현할 수 있는지 탐색합니다.

1 ~ 1000까지 3개의 삼각수의 합으로 표현할 수 있는지 탐색

1 : 1

2 : 1 + 1

3 : 1 + 1 + 1

4 : 1 + 3

5 : 3 + 1 + 1

6 : 3 + 3

7 : 3 + 3 + 1

....

1000 : 861 + 136 + 3

 

3. T개의 자연수를 3개의 삼각수의 합으로 표현 가능한지에 따라 결과를 출력합니다.

 

10	20	1000
6 + 3 + 1	X	861 + 136 + 3

1 0 1을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• n(n+1)/2점화식을 이용하여 1 ~ 44까지 삼각수를 미리 계산합니다.
• search함수를 이용하여 1~1000까지 3개의 삼각수의 합으로 표현가능한지 탐색합니다.
• T개의 자연수가 3개의 삼각수로 표현가능하면 1, 아니면 0을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 3개의 삼각수의 합으로 표현가능한지 탐색합니다.

 

import java.io.*;

public class Main{
    static int[] gauss;	//삼각수 저장 배열
    static boolean[] check;	//삼각수 3개로 표현할 수 있는지 확인 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        gauss = new int[45];
        check = new boolean[1001];
        //1~44의 삼각수 미리 계산하기
        for(int i=1;i<45;i++)
            gauss[i] = i*(i+1)/2;
        //1~1000까지 3개의 삼각수의 합으로 표현가능한지 탐색
        for(int i=1;i<1001;i++)
            search(0, i, i);
        int T = Integer.parseInt(br.readLine());
        //T개의 수가 3개로 표현 가능한지 확인
        for(int i=0;i<T;i++){
            int K = Integer.parseInt(br.readLine());
            if(check[K])	//삼각수 3개로 표현 가능
                bw.write("1\n");
            else		//삼각수 3개로 표현 불가능
                bw.write("0\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //삼각수 3개로 표현 가능한지 탐색하는 재귀함수
    static void search(int count, int cur, int index){
        if(count == 3){		//삼각수 3개를 사용했을 때
            if(cur == 0)	//삼각수 3개로 표현 가능할 때
                check[index] = true;
            return;
        }
        if(cur <= 0)	//삼각수 보다 커질 때
            return;
        //사용할 수 있는 삼각수 값들 모든 경우 탐색
        for(int i=1;i<45;i++){
            if(cur < gauss[i])	//더 큰 삼각수일 경우 중단
                break;
            search(count+1, cur - gauss[i], index);
        }
    }
}