[LeetCode] 633. Sum of Square Numbers

문제 출처: https://leetcode.com/problems/sum-of-square-numbers/

Sum of Square Numbers - LeetCode

---

문제

음이 아닌 정수 $c$ 가 주어지면, $a^2 + b^2 = c$ 인 두 정수 $a$ 와 $b$ 를 구하라.

예제

Input: c = 5
Output: true

Explanation: 1 * 1 + 2 * 2 = 5

Input: c = 1
Output: true

Input: c = 3
Output: false

---

풀이

어떤 조건을 만족하는 두 값을 찾기 위한 여러 방법 중에서 가장 손쉬운 것이 찾아야 하는 두 값 중 한 값을 고정시킨 다음에 다른 하나의 값을 확인하는 것이다. 찾아야 하는 조건인 $a^2 + b^2 = c$를 다음과 같이 생각할 수 있다.

 

$b^2 = c - a^2$

 

위와 같이 수식을 변경하고 나면, $a$의 값을 임의로 정함에 따라 자동적으로 $b$의 값을 구할 수 있게 되고 구해진 $b$가 정수인지 아닌지를 판단하여 문제의 답을 얻을 수 있다.

var judgeSquareSum = function(c) {
    let a = 0;
    while (c - (a*a) >= 0) {
        const b = c - (a * a);
        if (Number.isInteger(Math.sqrt(b))) { return true; }
        a += 1;
    }
    return false;
};

 

Github: 633.js

GitHub - opwe37/Algorithm-Study