프로그래머스 | Level 2 - 숫자의 표현

문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 "자연수 n을 연속한 자연수들로 표현 하는 방법"이 여러개라는 사실을 알게 되었습니다.

예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15

4 + 5 + 6 = 15

7 + 8 = 15

15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

풀이

처음에 찾은 규칙은 약수를 이용하면 될 것 같았다.

15의 약수의 개수 [1,3,5,15] -> 4개

 

14의 약수로 계산해보았을 때 

연속된 경우로 찾을 수 있는 것은 2가지인데,

2+3+4+5 = 14

14 = 14 

약수는 [1,2,7,14] 4개이다. 

 

완전탐색으로 풀어야하나 싶어서 Array.from으로 1부터 n까지 담긴 배열을 만들고, 누적해서 더하다가 15가 되면 카운팅을 한다. 되긴할 것 같은데 시간복잡도에서 별로인 방법이라고 생각했고, 약수를 이용하는 방법을 찾아보기로 했다.

 

해당 문제는

"주어진 수를 연속된 자연수의 합으로 표현하는 방법의 수"와

"주어진 수의 홀수인 약수의 갯수"는 같다.

주어진 수 를 연속된 자연수의 합으로 표현하는 방법 수 = 주어진 수의 약수 중에 홀수의 개수

는 공식을 이용한 풀이라고한다. 

 

약수 중에 홀수인 것의 갯수를 찾아야했다. 

*약수 : 어떤 수를 나누어 나머지 없이 떨어지는 수

15의 약수는 1, 3, 5, 15 이고 이 중 홀수는 4개이다. 

• 약수 1 => 연속하는 1개 자연수의 합으로 표현 가능
   15 = 15
• 약수 3 => 연속하는 3개 자연수의 합으로 표현 가능15를 3으로 나눈값인 5로 표현할 수 있다.
   5 + 5 + 5 = 15 => 3 + 4 + 5 = 15
• 약수 5 => 연속하는 5개 자연수의 합으로 표현 가능15를 5로 나눈값인 3으로 표현할 수 있다.
   3 + 3 + 3 + 3 + 3 = 15 => 1 + 2 + 3 + 4 + 5 = 15
• 약수 15 => 모든 홀수(2n+1)는 n과 n+1로 표현 가능
   7 + 8 = 15

 

 

코드

const solution = (n) => {
  let count = 0;

  for (let i = 0; i <= n; i++) {
    if (n % i === 0 && i % 2 !== 0) {
      count++;
    }
  }

  return count;
}