[백준] 17427번 : 약수의 합 2 (실버Ⅱ) by node.js

▷ 문제 :17427번 : 약수의 합 2 

17427번: 약수의 합 2

▷ 해결 날짜 : 2022.04.01
▷ 소요 시간 : 1시간
▷ 풀이 과정 :
문제는 그렇게 어렵지 않다.

주어진 숫자만큼 반복해서 돌면서 각 숫자의 약수의 합을 전부 더해준 값을 출력해주면 되는 문제였다.

 

그래서 문제는 5분 만에 풀었는데...

let fs = require('fs');
let input = fs.readFileSync('./text.txt').toString().split(' ');

let num = +input[0];
let sum = 0;

const getDivisorSum = (num) => {
    const divisors = [];
    for(let i = 1 ; i <= Math.sqrt(num) ; i++){
        if(num % i === 0) {
            divisors.push(i);
            if(num / i != i) divisors.push(num/i);
        }
    }

    return divisors.reduce((a, c) => a + c);
}

for(let i = 1 ; i <= num ; i++){
    sum += getDivisorSum(i);
}

console.log(sum)

당연히 이 해결 방법은 이 문제가 시간제한이 있다는 걸 몰랐었다.

하지만 시간제한이 있다해도 이 문제를 쉽게 풀진 못했다.(시간제한 너무 어렵다...)

 

결국 문제의 규칙을 찾아내기만 하면 해결방법은 매우 간단하다.

주어진 숫자가 10이라는 가정하에 각각의 약수 배열을 보면

[1] [1, 2] [1, 3] [1, 2, 4] [1, 5] [1, 2, 3, 6] [1, 7] [1, 2, 4, 8] [1, 3, 9] [1, 2, 5, 10]

이런 식으로 이루어져 있다.

 

1 => 10개 (10 / 1 = 10)

2 => 5개 (10 / 2 = 5)

3 => 3개 (10 / 3 = 3.xxx)

4 => 2개 (10 / 4 = 2.xxx)

5 => 2개 (10 / 5 = 2)

6 => 1개 (10 / 6 = 1.xxx)

7 => 1개 (10 / 7 = 1.xxx)

8 => 1개 (10 / 8 = 1.xxx)

9 => 1개 (10 / 9 = 1.xxx)

10 => 1개 (10 / 10 = 1)

 

이 규칙대로 풀어보면 Math.floor(num/i)라는 걸 알 수 있다.

 

▷ 구현

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

let num = +input[0];
let sum = 0;
for (let i = 1; i <= num; ++i) {
    sum += i * Math.floor((num / i));
}

console.log(sum);

 

▷ 복기 :

효율성 문제는 아무리 봐도 적응이 안되네, 그냥 진짜 문제를 많이 풀어보는 게 정답인 거 같다.