[알고리즘/javascript] 백준 10448번: 유레카 이론

문제 바로가기

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

 

✏️ Problem

삼각수 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개의 삼각수가 모두 달라야 할 필요는 없다.

 

🧑‍💻 Solution

const [testCase, ...testCaseArr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);

for(let i = 0; i < testCase; i++) {
    console.log(findTriangularNum(testCaseArr[i]));
}

function findTriangularNum(num) {
    for(let i = 1; i < num-1; i++) {
        for(let j = 1; j < num-1; j++) {
            for(let k = 1; k < num-1; k++) {
                if(i+j+k === num && checkEureka(i) && checkEureka(j) && checkEureka(k)) return 1;
            }
        } 
    }
    return 0;
}
function checkEureka(num) {
    let sum = 0;
    for(let i = 1; i <= num; i++) {
        sum += i;
        if(sum === num) return true;
    }
    
    return false;
}

 

문제를 읽고 난 후 이해하고 설계한 과정은 다음과 같다. 간단하게 두 단계로 나눌 수 있다.

1. 입력 값을 세 정수의 합으로 구성한다.

2. 세 정수가 삼각수인지 확인한다.

 

먼저 세 정수의 합으로 구성하기 위해 삼중 for문을 사용했다. 반복문을 돌면서 i + j + k가 입력값과 같은 경우를 잡는다.

그리고 입력값이 같은 경우에 i, j, k 세 정수가 삼각수인지 확인한다.

 

삼각수인지 아닌지를 확인하기 위해서는 삼각수를 이해해야 한다. 삼각수의 패턴은 다음과 같다.

T₁ = 1

T₂ = 3 = 1 + 2 = T₁ + 2

T₃ = 6 = 1 + 2 + 3 = T₂ + 3

T₄ = 10 = 1 + 2 + 3 + 4 = T₃ + 4

T₅ = 15 = 1 + 2 + 3 + 4 + 5 = T₄ + 5

•••

Tn = 1 + 2 + 3 + ••• + (n-1) + n =  Tn-1 + n

 

 

checkEureka 함수에서 이와 같은 확인 과정을 거친다.

1부터 파라미터 num까지의 합을 진행하고 그 합이 파라미터 num과 같다면 그 수는 삼각수이다.

 

 

알고리즘 초보입니다.. 틀린 부분이나 개선해야 할 부분이 있다면 편하게 댓글 부탁드립니다🥲