백준 10488 : 유레카 이론

💡기본 정보

유형
: 브루트포스
풀이 날짜
: 2025년 01월 08일 
풀이방법 한줄 요약
:삼각수를 구하고 세개를 더해서 해당되는지 확인하기 

 

💡문제에서 구해야 할 것
삼각수  Tn 는 다음 그림과 같이 일정한 모양의 규칙을 갖는 점들의 모음으로 표현 가능

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

  - 입력 : 테스트 케이스의 개수는 입력 첫 번째 줄에 주어짐 . 각 테스트 케이스는 한 줄에 자연수 K가 하나씩 포함되어있는 T개의 라인
    출력 : K가 정확히 3개의 삼각 수의 합으로 표현될 수 있다면 1 , 그렇지 않다면 0 출력 

 

💡알고리즘 설계
- 삼각수를 구함 ( 45의 삼각수가 1000을 넘기에 45까지만 구함)
- 삼각수를 가지고 합이 표현되는지 체크함

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0, "utf8").toString().split("\n");
const n = parseInt(input[0]);
const nums = input.slice(1, n + 1).map(Number);

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

  let results = [];
  for (i of nums) {
    let isEureka = 0;
    for (one of tri_list) {
      for (two of tri_list) {
        for (three of tri_list) {
          if (one + two + three === parseInt(i)) {
            isEureka = 1;
            break;
          }
        }
        if (isEureka === 1) break;
      }
      if (isEureka === 1) break;
    }
    results.push(isEureka);
  }

  return results;
}
const answer = Eureka();
if (answer) {
  console.log(answer.join("\n"));
}

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

- 첫 번째 테스트 케이스 계산 후 바로 break; 됨. 

 

💡 다른 풀이 or 기억할정보

  for (i of nums) {
    let isEureka = 0;
    for (one of tri_list) {
      for (two of tri_list) {
        for (three of tri_list) {
          if (one + two + three === parseInt(i)) {
            isEureka = 1;
            break;
          }
        }
        if (isEureka === 1) break;
      }
      if (isEureka === 1) break;

3개의 for문을 사용했으므로 if 문을 하나만 사용하면 바로 break될 수 있음 이를 유의해서 구현할 것 .