[백준] 10448 유레카 이론

[Bronze 1] 10448 유레카 이론

문제 링크

구분

알고리즘 > 완전탐색

풀이 요약

세 개의 삼각수 합으로 표현되는 문자임을 알아내기 위해 모든 가능한 조합을 검사해서 각 숫자가 삼각수이면 true, 그렇지 않으면 false를 반환하는 문제

나의 풀이

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

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

function TriangleNum(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 && Eureka(i) && Eureka(j) && Eureka(k)) return 1;
      }
    }
  }
  return 0;
}

function Eureka(num) {
  let sum = 0;
  for (let i = 1; i <= num; i++) {
    sum += i;
    if (sum === num) {
      return true;
    }
  }
  return false;
}

삼각수는 각 숫자가 이전 값에 1씩 더해진 합으로 표현됩니다.

예를들면,

• 1=1
• 3=1+2
• 6=1+2+3
• 10=1+2+3+4

Eureka 함수는 숫자 num이 삼각수인지 확인하는 함수입니다.

또 TriangleNum 함수는 i,j,k라는 세 숫자의 조합으로 num이 표현될 수 있는지를 확인하는 함수입니다.

예를 들어 num=7 일때,

i+j+k=1+3+3=7이 되고, 각 숫자가 삼각수인지 Eureka함수로 확인하면 1,3,3 모두 삼각수 이므로 조건을 만족합니다.

이 조건을 만족하면 1을 반환하고 조건을 만족하지 않으면 0을 반환합니다.

배운점

각 테스트케이스에 대해 정확히 한 라인만 출력해야하기 때문에 구조분해 할당(const [testCase, ...testCaseArr])을 적용해서 데이터를 쉽게 받아올 수 있었습니다.

느낀점

브론즈 1 문제임에도 불구하고 시간이 꽤 오래 걸렸던 문제였습니다. 완전 탐색과 이분탐색을 더 공부하여 효율적으로 풀어나가야겠습니다 !