[BOJ] 17626 - Four Squares (Python, JavaScript)

 

 

아이디어 #1

 

라그랑주에 의해 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명되었으므로

7453번 - 합이 0인 네 정수처럼 두 제곱수를 더한 값들에서 투 포인터로 합이 n이 되는 네 제곱수를 찾는다.

 

 

풀이 #1 (Python)

 

딕셔너리 cnt_dict에 두 제곱수 합을 키로, 0이 아닌 제곱수의 개수를 값으로 저장한다.

입력 n이 50,000 이하로 주어지므로 제곱수의 제곱근은 223 이하로 설정하고, 0은 제곱수가 아닌 것으로 본다.

 

세트 numbers에 두 제곱수 합들을 저장한 후 numbers를 오름차순으로 정렬한 리스트로 대체한다.

투 포인터를 이용해 numbers에서 네 제곱수 합이 n인 경우를 찾아 최소 제곱수 개수를 갱신해 나간다.

 

n = int(input())
cnt_dict = dict()
numbers = set()
for i in range(224):
    for j in range(224):
        if i*i+j*j > n:
            break
        cnt_dict[i*i+j*j] = min(cnt_dict.get(i*i+j*j, 4), sum([i > 0, j > 0]))
        numbers.add(i*i+j*j)

numbers = sorted(numbers)
s = 0
e = len(numbers)-1
res = 4
while s < e:
    total = numbers[s]+numbers[e]
    if total < n:
        s += 1
    elif total > n:
        e -= 1
    else:
        res = min(res, cnt_dict.get(numbers[s], 4)+cnt_dict.get(numbers[e], 4))
        s += 1
        e -= 1
print(res)

 

 

 

아이디어 #2

 

다른 분의 코드를 참고해보니 라그랑주의 네 제곱수 정리를 이용하면 더 효율적으로 구현할 수 있었다.

n과 k가 정수일 때 4^n(8n+7)은 3개의 제곱수 합으로 나타낼 수 없지만, 나머지 정수들은 나타낼 수 있다.

따라서 입력으로 주어진 수를 제곱수와 두 제곱수 합에서 찾고, 나머지는 네 제곱수 정리로 찾는다.

 

 

풀이 #2 (Python)

 

제곱수를 리스트 numbers에 추가하면서 중간에 n을 찾으면 1을 출력하고 종료한다.

제곱수에서 n을 찾지 못하면 n에서 제곱수를 뺀 나머지를 numbers에서 찾고, 있으면 2를 출력하고 종료한다.

n에서 제곱수를 뺀 나머지도 찾지 못하면 n이 4로 나누어 떨어지는 동안 n을 4로 나눈 후,

그 나머지를 8로 나눈 나머지가 7이면 4, 그렇지 않으면 3을 출력한다.

 

n = int(input())
numbers = []
for i in range(1, 224):
    if i*i == n:
        print(1)
        break
    numbers.append(i*i)
else:
    for num in numbers:
        if n-num in numbers:
            print(2)
            break
    else:
        while n%4 == 0:
            n //= 4
        if n%8 == 7:
            print(4)
        else:
            print(3)

 

 

 

풀이 #3 (JavaScript)

 

풀이 #2와 같은 방식으로 동작하며, 파이썬처럼 for-else문이 없어 결과값을 저장하는 res로 분기를 처리한다.

 

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

let n = Number(input);
let numbers = [];
let res = 0;
for (let i=0; i<224; i++) {
    if (i*i === n) {
        res = 1;
        break
    }
    numbers.push(i*i);
}
if (res === 0) {
    for (let num of numbers) {
        if (numbers.includes(n-num)) {
            res = 2;
            break;
        }
    }
    if (res === 0) {
        while (n%4 === 0) n /= 4;
        if (n%8 === 7) res = 4;
        else res = 3;
    }
}
console.log(res);