프로그래머스 숫자의 표현 자바스크립트 알고리즘 풀이

문제

문제 링크

나의 풀이

아이디어

연속된 숫자끼리 더해야 하므로,

• 숫자끼리 더한 합이 sum보다 작을 경우?
  • 다음 자연수로 넘어가서 더하기
• 숫자끼리 더한 합이 sum과 동일할 경우?
  • ++count 후 break
• 숫자끼리 더한 합이 sum보다 클 경우?
  • break

    코드

    function solution(n) {
      let answer = 1; // 자기 자신
      for(let i = 1; i <= n; ++i) { 
      let sum = i;
      for(let j = i+1; j <= n; ++j){
          sum += j;
          if(sum === n) {
              ++answer;
              break;
          }
          else if(sum > n) {
              break;
          }
      }
      }
      return answer;
    }
    

다른 사람 풀이

이번 문제는 유난히 수학 괴물(?)들의 풀이가 많았다.

function expressions(num) {
    var answer = 0;
    for (var i = 1; i <= num; i++) {
        if ((num % i == 0) && (i % 2 == 1)) {
            answer++;
        }
    }
    return answer;
}

등차수열의 합 공식에서 도출한 홀수 약수 개수와 연속된 자연수의 합 개수의 상관관계를 이용한 풀이.
연속된 자연수의 개수가 k이고 합이 시작하는 자연수를 m이라고 할 때, k(2m+k−1)=2n 이라는 공식이 나온다.
이때 k가 홀수인 경우 2m+k-1도 홀수이기 때문에 k는 n의 홀수 약수가 된다.
n을 연속된 자연수의 합으로 나타내는 방법의 수는 n의 홀수 약수의 개수와 동일해진다.