[BOJ] 6131번 : 완전 제곱수

백준 6131번 : 완전 제곱수

🔗 문제 링크

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

6131번: 완전 제곱수

 

---

💬 문제

 제곱 과  완전탐색(브루트포스) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 어떤 정수 A와 B가 있을 때, A의 제곱은 B의 제곱보다 N만큼 크다.
   
   - A는 B보다 작거나 같고, A와 B는 500보다 작다
   
   
2. N이 주어질 때, N만큼 차이나는 A와 B의 쌍의 개수를 구해준다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 정수 하나가 주어진다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 총 2가지 방식으로 풀 수 있다.

🔑 풀이1 : A와 B 범위 내에서 완전 탐색

• for문으로 500까지 범위 내에서 A와 B에 값을 할당해준다.
  단 
  - B는 A보다 작거나 같아야 하므로, A의 스코프보다 상위에서 값이 할당되어야 한다.
  
  
• A의 제곱이 B의 제곱보다 N만큼 크다면, cnt의 개수를 증가시켜준다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

console.log(solution(parseInt(input)));

function solution(N) {
  let A, B;
  let cnt = 0;  // 제곱의 차이가 N인 경우의 수
  for (let i=1; i <= 500; i++) {  // B에 값 할당
    B = i;
    for (let j=1; j <= 500; j++) {  // A에 값 할당
      A = j;
      if ((A * A) === (B * B + N)) {  // 제곱의 차이가 N일때
        cnt++;
      }
    }
  }
  return cnt;
}

 

시간은 다음과 같이 걸렸다.

 

 

👣 예제를 참고한 풀이

예제처럼 A의 제곱과 B의 제곱이 15가 될 때는 총 2가지 경우다.

B = 1, A = 4일때 그리고 B = 7, A = 8일 때에 제곱의 차이가 15가 된다.

 

if문 안에서 조건에 부합하는 A와 B를 출력해보면 알 수 있다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

console.log(solution(parseInt(input)));

function solution(N) {
  let A, B;
  let cnt = 0;  // 제곱의 차이가 N인 경우의 수
  for (let i=1; i <= 500; i++) {  // B에 값 할당
    B = i;
    for (let j=1; j <= 500; j++) {  // A에 값 할당
      A = j;
      if ((A * A) === (B * B + N)) {  // 제곱의 차이가 N일때
        console.log(`A=${A}, B=${B}`)
        cnt++;
      }
    }
  }
  return cnt;
}

 

---

🔑 풀이2 : 제곱 / 제곱근 메서드로 완전 탐색

• B의 제곱에 N을 더한 값이 A의 제곱이다. 따라서 이 수(B의 제곱+N)의 제곱근이 정수라면 B의 제곱과 A의 제곱의 차이는 N이 된다.
  
  -  Math.pow(i, n) 는 i의 n제곱 값을 구하는 메서드다
  -  Math.sqrt(n) 는 n의 제곱근 값을 구하는 메서드다
  -  Number.isInteger(n) 는 n이 정수인지 판별하는 메서드다
  
  

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

console.log(solution(parseInt(input)));

function solution(N) {
  let cnt = 0;  // 제곱의 차이가 N인 경우의 수

  for (let B=1; B <= 500; B++) {
    // B의 제곱에 N을 더한 것이 완전제곱수의 제곱근이 될 때
    if (Number.isInteger(Math.sqrt(Math.pow(B, 2) + N))) {
      cnt++;
    }
  }
  return cnt;
}

 

시간은 이중 for문을 돌리는 것보다 확실히 빨라졌다.

 

 

👣 예제를 참고한 풀이

예제를 통해 좀 더 쉽게 설명해보자. N이 15일때, B값이 변함에 따라 A가 어떻게 달라지는지 살펴보자.

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

console.log(solution(parseInt(input)));

function solution(N) {
  let cnt = 0;  // 제곱의 차이가 N인 경우의 수

  for (let B=1; B <= 5; B++) {
    // B의 제곱에 N을 더한 것이 완전제곱수의 제곱근이 될 때
    let A = Math.sqrt(Math.pow(B, 2) + N);
    console.log(`A=${A}, B=${B}`);
    if (Number.isInteger(A)) {
      cnt++;
    }
  }
  return cnt;
}

 

만약 B가 1에서 5까지일 때, 아래처럼 결과가 출력될 것이다.

A는 정수여야 하므로,  Number.isInteger(n) 메서드로 판별해주면 된다. 이렇게 B를 500 범위까지 넣어보면 된다.

이렇게 되면 풀이 1번에선 500 x 500, 25만번 확인해줘야 하지만, 이 방법으로는 500번만 확인하면 되니 시간이 훨씬 빨라진다. 

A=4, B=1
A=4.358898943540674, B=2
A=4.898979485566356, B=3
A=5.5677643628300215, B=4
A=6.324555320336759, B=5