문제
삼각수 Tn(n ≥ 1)는 그림에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.
자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.
Tn = 1 + 2 + 3 + ... + n = n(n+1)/2
1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,
4 = T1 + T2
5 = T1 + T1 + T2
6 = T2 + T2 or 6 = T3
10 = T1 + T2 + T3 or 10 = T4
이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.
자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.
입력
프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.
출력
프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.
예제 입력
3
10
20
1000
예제 출력
1
0
1
내가 했던 풀이 방법
- array에 Tn을 계산한 결과를 넣어둔다. (이때 n(n+1)/2 값이 1000을 넘으면 탈출한다. 왜냐? K가 1000까지이기 때문에 그 이상의 값들은 필요 없으므로)
- Eureka를 false로 초기화한 후, 계산할 자연수를 입력받는다.
- 3중 for문을 통해 num = Δ + Δ + Δ로 표현되는 경우를 찾는다.
- 만약 num = Δ + Δ + Δ로 표현되는 경우가 있다면, Eureka를 true로 바꾼 후, for문에서 탈출한다.
- Eureka의 값에 따라 1과 0을 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class b10448 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int test_case = Integer.parseInt(br.readLine());
int number;
ArrayList<Integer> array = new ArrayList<>();
int cal;
for (int i=1; ; i++) {
cal = (i*(i+1))/2;
if(cal>1000) break;
else array.add(cal);
}
boolean Eureka;
for(int i=0; i<test_case; i++) {
Eureka = false;
number = Integer.parseInt(br.readLine());
for(int j=0; j<array.size(); j++) {
for(int k=0; k<array.size(); k++) {
for(int l=0; l<array.size(); l++) {
cal = array.get(j)+array.get(k)+array.get(l);
if(cal==number) {
Eureka = true;
break;
}
}
}
}
if(Eureka) {
System.out.println(1);
} else {
System.out.println(0);
}
}
}
}
회고
이제 보니 for문 탈출이 잘 안 되는 것 같은데 틀리지 않을 걸 보면 속도적인 부분에서 큰 문제는 없나보군... brute force 알고리즘을 이용한 문제라고 해서 이 부분에 대해서도 정리하고 끝내보도록 하겠다. 디테일한 부분은 그와 관련된 문제를 풀이할 때 조금씩 정리해야지.
brute force
brute: 무식한, force: 힘 -> 무식한 힘으로 해석할 수 있다.
완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.
선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.
참고 자료
