백준 10448번: 유레카 이론

완전 탐색에 대해 공부하기 위해 처음 주어진 문제가 백준 10448번 유레카 이론 문제였습니다.

삼각수를 구하는 공식을 이용해 입력된 K이 3개의 삼각수의 합으로 표현될 수 있는지를 확인해 1 또는 0을 출력하는 문제입니다.

 

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

---

 

1. 문제 풀이 접근

우선 가장 처음 문제를 접했을 때 들었던 궁금증입니다.

" 삼각수 공식을 모르는 상태로 이 문제를 받게되면, 어떻게 접근해야 하는가 ? "

다행히도 문제에서는 삼각수 공식이 T(n) = 1 + 2 + 3 + ... + n = n(n+1)/2 라고 알려주고 있습니다.

이것을 모르고 저는 처음에 삼각수 공식을 T(n) = n + T(n-1)로 접근했었는데,

이렇게 작성하고 코드를 짜려고 하니 뒤의 T(n-1)을 기억해가며 코드를 작성해야하는 상황에 놓이게 되었습니다.(재귀적 정의)

 

기본적으로 누적합 공식은 수학과정 중 수열을 배우는 파트에서 배우게 된다는데, 이를 모르고 접근했다고 가정했을 때

n = 1 → 1

n = 2 → 3

n = 3 → 6

...

n = 5 → 15

순으로 나열해가며 유추하는 방법이 있는데, 이런상황에 마주한 것 자체에서 "누적 합이고 공식이 있을 수 있겠다!"라고 앞으로 떠올릴 수 있으면 바람직하게 접근한것으로 보고 다음으로 넘어갑니다.

 

다음은 입력받은 수를 바탕으로 " 입력된 수가 삼각수 세 개의 합으로 표현될 수 있는가? "에 대한 접근입니다.

첫 풀이는 이렇게 접근했습니다.

 

[ 첫 접근 방식 ]

1. 삼각수가 저장된 배열 만들기

2. 입력된 k 미만 중 가장 큰 삼각수 찾기

3. k에서 해당 삼각수를 빼기

4. 2~3을 세 번 반복, 반복 도중 삼각수를 뺀 결과가 0이되면 0 출력

5. 세 번 반복 후, 삼각수를 뺀 결과가 0이면 1 출력

 

이를 바탕으로 코드를 작성하니 문제가 생겼습니다.

2-3번과정 k 미만 가장 큰 삼각수를 찾아 해당 삼각수를 빼기는 " Greedy(탐욕적) " 해결 방식으로 이 방법을 사용하면 3개의 삼각수 합을 만들지 못할 수 있다는 문제였습니다.

k=9 일 때, 9는 삼각수 1, 3, 6 세 개의 삼각수로 조합될 수 있지만,

위 접근방식으로 가장 큰 삼각수 6을 제외하면 9 - 6 = 3, 다음 가장 큰 삼각수 3, 3 - 3 = 0 으로 2개만에 끝나버렸습니다.

 

따라서 " 완전 탐색 "의 의도에 맞게 모든 경우를 확인하는 방식으로 고쳐봅니다.

 

1. 삼각수가 저장된 배열 만들기

2. 입력된 inputNum에 대해 모든 삼각수 배열을 순회하며 i, j, k의 합이 inputNum이 되는지 확인하기

3. 된다면 1을 출력, 안된다면 0을 출력

 

---

2. 코드 작성하기

변화된 접근방식으로 작성된 코드는 다음과 같습니다.

package algorithms.boj.bruteForce;

import java.util.Scanner;

public class Q10448_2 {

	public static void main(String[] args){
		int[] triangleNumsArray = setTriangleArray();
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();

		for(int t = 0; t < T; t++){
			int inputNum = scan.nextInt();
			int ans = triangleTest(inputNum, triangleNumsArray);
			System.out.println(ans);
		}

	}

	//	먼저, 삼각수 배열을 만드는 코드를 작성해본다.
	//	삼각수 공식은 T(n) = n*(n+1)/2 임을 기억하자 !
	public static int[] setTriangleArray(){
		//	그런데 삼각수 배열의 최대 길이는 삼각수가 1000이 넘지 않는 T(n) n만큼의 길이, 따라서 이 n값을 먼저 찾아야 한다.
		int n = 1;
		while(true){
			int triangleNum = n * (n + 1) / 2;
			if(triangleNum > 1000) break;
			n++;
		}

		//	구한 n을 가지고 배열을 선언하고, 해당 배열 안에 삼각수를 저장한다.
		int[] triangleNumsArray = new int[n-1];
		for(int i = 1; i <= triangleNumsArray.length; i++) {
			triangleNumsArray[i-1] = i * (i + 1) / 2;
		}
		return triangleNumsArray;
	}

	public static int triangleTest(int inputNum, int[] triangleNumsArray){
		//	다음, 입력받은 K 값을 이용해 삼각수 세개로 표현이 가능한지 알아보는 완전탐색 for문을 작성한다.
		for(int i = 0; i < triangleNumsArray.length; i++) {
			//	첫번째 삼각수
			for (int j = 0; j < triangleNumsArray.length; j++) {
				//	두번째 삼각수
				for(int k = 0; k < triangleNumsArray.length; k++) {
					//	세번째 삼각수
					if((triangleNumsArray[i] + triangleNumsArray[j] + triangleNumsArray[k]) == inputNum){
						return 1;
					}

				}
			}
		}
		return 0;
	}


}

먼저 삼각수 배열을 만드는 메서드를 실행하고,

입력된 숫자와 만들어진 삼각수 배열을 이용해 삼각수 세 개의 합으로 표현이 되는지 확인 후 1 또는 0을 리턴해 이를 출력하는 방식의 코드입니다.

 

시간복잡도는 O(T(테스트 케이스 갯수) * ((삼각수의 개수) + (삼각수의 개수^3))) = O(T*(N + N^3)) 입니다.

입력값의 범위는 3~1000 입니다.

 

 

작동이 잘 되고, BOJ도 통과되었습니다.

---

3. 코드 개선하기(다른 풀이방법)

시간복잡도를 확인해보면 테스트 케이스 갯수가 앞에 곱해지는데

모든 삼각수의 개별 합에 대한 배열을 만들어놓고 테스트 케이스가 이 합 배열 안에 있는지 확인만 하면

테스트 케이스때마다 삼각수의 갯수 합을 구하는 반복을 줄일 수 있다.

HashSet<Integer> possibleSums = new HashSet<>();

for(int i = 0; i < triangleNumsArray.length; i++){
    for(int j = 0; j < triangleNumsArray.length; j++){
        for(int k = 0; k < triangleNumsArray.length; k++){
            int sum = triangleNumsArray[i] + triangleNumsArray[j] + triangleNumsArray[k];
            possibleSums.add(sum);
        }
    }
}

for(int t = 0; t < possibleSums.size(); t++){
    int K = scan.nextInt();
    if(possibleSums.contains(K)){
        System.out.println("1");
    }else{
        System.out.println("0");
    }
}

 

코드를 다음과 같이 개선해 추가하면, O(T * N^3)의 복잡도를 O(T + N^3)으로 줄일 수 있다 !