[Baekjoon] 17427 약수의 합 2(자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

17427번: 약수의 합 2

---

🤔 문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제 입력 1

1

예제 출력 1

1

예제 입력 2

2

예제 출력 2

4

예제 입력 3

10

예제 출력 3

87

예제 입력 4

70

예제 출력 4

4065

예제 입력 5

10000

예제 출력 5

82256014

---

정답 코드

답안 1

답안 2

---

문제 풀이

 어떤 자연수의 약수를 이루는 수들 간의 규칙성을 찾아내야 풀 수 있는 문제이다. 아래와 같이 무작정 2중 for 반복문을 돌리면 시간 초과가 뜬다.

시간초과

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

const n = parseInt(input);

// 시간초과
const solution1 = (num) => {
    let result = 0;
    for (let i = 1; i <= num; i++) {
        let sum = 0;
        for (let j = 1; j <= i; j++) {
            if (i % j === 0) sum += j;
        }
        result += sum;
    }
    return result;
};

console.log('solution1');
console.log(solution1(n));

 

 여기서 말하는 규칙성이란 특정 자연수 N보다 작은 수 K는 N / K번만큼 등장한다는 것이다. 특정 자연수가 10이라면 10보다 작은 수의 약수 및 계산 과정은 다음과 같다.

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

주어진 수 N: 10

0(이전값) + 1(N보다 작은 수 K) * 10(등장횟수) = 10(결괏값)
10(이전값) + 2(N보다 작은 수 K) * 5(등장횟수) = 20(결괏값)
20(이전값) + 3(N보다 작은 수 K) * 3(등장횟수) = 29(결괏값)
29(이전값) + 4(N보다 작은 수 K) * 2(등장횟수) = 37(결괏값)
37(이전값) + 5(N보다 작은 수 K) * 2(등장횟수) = 47(결괏값)
47(이전값) + 6(N보다 작은 수 K) * 1(등장횟수) = 53(결괏값)
53(이전값) + 7(N보다 작은 수 K) * 1(등장횟수) = 60(결괏값)
60(이전값) + 8(N보다 작은 수 K) * 1(등장횟수) = 68(결괏값)
68(이전값) + 9(N보다 작은 수 K) * 1(등장횟수) = 77(결괏값)
77(이전값) + 10(N보다 작은 수 K) * 1(등장횟수) = 87(결괏값)

  위와 같은 규칙을 적용하여 풀어야 하는 문제이다.

---

함께 보기

https://mine-it-record.tistory.com/523

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

https://data-flower.tistory.com/95

[백준 17427번] 약수의 합 2 - 파이썬