[BOJ] 9506번 : 약수들의 합

백준 9506번 : 약수들의 합

🔗 문제 링크

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

9506번: 약수들의 합

 

---

💬 문제

 약수 와  완전수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 어떤 숫자 n이 주어졌을 때, 자신(n)을 제외한 모든 약수를 구해준다.
   
   - 자신(n)을 제외한 약수의 합이 n과 같다면 그 수는 완전수이다.
       
2. n의 제외한 모든 약수의 합을 구해주고, 그 값이 n과 같은지 비교해준다.
   
   - 그 수가 완전수라면, n = 약수 + ... + 약수로 출력해준다 (오름차순)
   - 아니라면, n is NOT perfect. 를 출력해준다.
   
   

 

---

💡 입력값 받아오기

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

이 문제에서는 완전수인지 판단해야 할 수가 줄바꿈을 기준으로 주어지고, 맨 마지막에는 -1이 주어진다.

줄바꿈을 기준으로 각 수를 잘라주고, 마지막의 -1은 제거해준다.

 

 

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

https://valueengine.tistory.com/2

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

 

728x90

 

---

💻 풀이

이 문제는 나누는 수의 범위에 따라 총 2가지 방식으로 풀 수  있다.

🔑 풀이1 : 모든 수로 나눠 약수 구하기

• 줄바꿈을 기준으로 각 숫자(num)를 잘라주고, 맨 마지막 숫자 -1을 제거해준다.
  
  
• for문으로 2부터 num 이전까지 모든 수로 num을 나눠 약수 배열 divosor에 채워준다.
  
  - 1은 항상 약수이므로, 미리 약수 배열 divisor에 넣어준다.
  
  
•  reduce() 로 모든 약수의 합을 구하고, num과 비교해 완전수인지 판단해준다.
  
  - 완전수라면,  n = 약수 + ... + 약수로 출력해준다 (오름차순)
  - 아니라면, n is NOT perfect. 를 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
input.pop();  // 맨 끝 -1 제거

console.log(input.map(function solution(num) {
  const divisor = [1];  // 약수에 항상 1이 있으므로

  for (let i=2; i < num; i++) {   // 제곱근 범위
    if (num % i === 0) {
      divisor.push(i);        // 약수 i
    }
  }
  if (divisor.reduce((acc, cur) => acc + cur, 0) === num) {  // 완전수
    return `${num} = ` + divisor.join(' + ');
  } else {
    return `${num} is NOT perfect.`;
  }
}).join('\n'));

 

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

 

 

---

🔑 풀이2 : 제곱근 범위까지만 나눠 약수 구하기

• 줄바꿈을 기준으로 각 숫자(num)를 잘라주고, 맨 마지막 숫자 -1을 제거해준다.
  
  
• for문으로 2부터 num의 제곱근까지 수로 num을 나눠 약수 배열 divosor에 채워준다.
  
  -  Math.sqrt()  메서드로 제곱근을 구할 수 있다.
  - 1은 항상 약수이므로, 미리 약수 배열 divisor에 넣어준다.
  
  
•  reduce() 로 모든 약수의 합을 구하고, num과 비교해 완전수인지 판단해준다.
  
  - 완전수라면, "n = 약수 + ... + 약수"로 출력해준다. 이때 정렬이 안 되어 있으므로,  sort() 로 정렬해준다.
  - 아니라면, "n is NOT perfect."를 출력해준다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
input.pop();  // 맨 끝 -1 제거

console.log(input.map(function solution(num) {
  const divisor = [1];  // 약수에 항상 1이 있으므로

  for (let i=2; i <= Math.sqrt(num); i++) {   // 제곱근 범위
    if (num % i === 0) {
      divisor.push(i);        // 약수 i
      divisor.push(num / i);  // i와 곱했을때 num이 되는 약수
    }
  }
  if (divisor.reduce((acc, cur) => acc + cur, 0) === num) {  // 완전수
    return `${num} = ` + divisor.sort((a,b) => a - b).join(' + ');
  } else {
    return `${num} is NOT perfect.`;
  }
}).join('\n'));

 

제곱근까지만 for문을 돌렸기에 시간 효율이 더 나아졌다.