백준 10448(JAVA) - 유레카 이론

10448번: 유레카 이론 (acmicpc.net)

10448번: 유레카 이론

 

백준 10448 유레카 이론이다. 문제에서 대단한 함정이 하나 있는데 배열 크기를 45로 측정할 수 있다는 것이다. 이 부분은 범위가 1000이라는 것에 초점을 맞춰서 i*(i+1)/2 = 1000 이 되는 방정식을 풀어보면 i가 44라는 것을 파악할 수 있다. 이것을 통해서 크기를 45로 잡고 시작할 수 있다.

 

※ 알고리즘

1. 1000을 통해서 배열 크기가 45인 배열을 만들어 낸다.

2. triangleSum이라는 삼각수를 만들 수 있는 함수를 만든다.

3. 함수의 알고리즘 : 3중 for문으로 sum 값을 만들어 내어 n과 비교하여 같으면 1, 다르면 0이다.

4. 함수를 result에 넣고 출력하면 끝

 

package selftest;

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

public class Main_10448 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int triangle[] = new int[45];
		
		for(int i = 0; i<45; i++) {
			triangle[i] = i*(i+1)/2;
		}
		for(int i = 0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			int result = triangleSum(num, triangle);
			sb.append(result).append('\n');
		}
		System.out.println(sb.toString());
	}
	
	public static int triangleSum(int n, int triangle[]) {
		for(int i = 1; i<45; i++) {
			for(int j = 1; j<45; j++) {
				for(int k = 1; k<45; k++) {
					int sum = triangle[i] + triangle[j] + triangle[k];
					if(sum == n) {
						return 1;
					}
				}
			}
		}
		return 0;
	}

}

이 문제는 문제의 범위를 통한 배열 크기, 3중 for문의 이용이 가장 핵심적인 키워드 였지 않나 싶다.