백준 10448: 유레카 이론 - javascript (완전 탐색)

문제 출처 

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

10448번: 유레카 이론

문제

삼각수 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을 출력한다.

문제 풀이 힌트 

삼각수 세개 합으로 구할 수 있는지 완전 탐색의 방법을 사용해야 한다. 

문제 풀이 코드 

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; 
const input = require("fs").readFileSync(path).toString().trim().split('\n');

const n = input[0];
let nums = input.slice(1);

let tri_list=[];
for(var i = 1; i < 45; i++){
    tri_list.push(i * (i + 1) / 2)
}

let result = 0;

for(i of nums){
    result = 0;
    for (one of tri_list){
        for (two of tri_list){
            for (three of tri_list){
                if (one + two + three === parseInt(i)){
                    result = 1;
                }
            }
        }
    }
    console.log(result)
}

의사 코드 추가 

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; 
const input = require("fs").readFileSync(path).toString().trim().split('\n');

const n = input[0]; //주어진 수 개수 
let nums = input.slice(1);

let tri_list=[]; //k의 최댓값은 1000이니 1000까지의 모든 삼각수를 구해 tri_list[]에 담기
for(var i = 1; i < 45; i++){
    tri_list.push(i * (i + 1) / 2) //삼각수 개수 구하는 공식은 문제에 제시되어있음 
}

let result = 0; 

for(i of nums){
    result = 0; //세개의 합으로 안구해질 때 0의 값
    for (one of tri_list){
        for (two of tri_list){
            for (three of tri_list){
                if (one + two + three === parseInt(i)){
                    result = 1; //세개의 합으로 구해질 때 1의 값으로 바꾸기 
                }
            }
        }
    }
    console.log(result)
}