<Level 2> 숫자의 표현 with JS

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

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

제한사항

• n은 10,000 이하의 자연수 입니다.

 

function solution(n) {
  var answer = 0;
  let right = 1;
  let sum = 1;
  for (let left = 1; left <= n; left++) {
    while (sum < n) {
      right++;
      sum += right;
    }
    if (sum === n) answer += 1;
    sum -= left;
  }
  return answer;
}

 

- 하나하나 더해가며 확인하면 시간초과가 발생하는 문제로 보인다. 채점시 효율성을 체크하는 것으로 보아 10000이라는 제한사항은 괜히 주어진 것이 아닐 것이다.

 

- 필자는 투포인터로 해결하였다. left와 right라는 포인터를 사용하여 right가 커져가며 sum에 더해나갔다. 만약 sum이 n보다 크거나 작아지면 n과 같아졌는지 체크한다.

 

- left를 1 늘리고 left의 숫자는 sum에서 빼주고 위의 과정을 반복한다.

 

- 다른사람의 풀이를 보고 n이 가진 홀수약수의 갯수가 연속된 숫자의 합으로 표현되는 경우의 수와 같다는 것을 알게되었다. 기억해두면 쓸 곳이 있을 것 같아서 여기에 메모해둔다.

 

 

---

 

참고

 

코딩테스트 연습 - 숫자의 표현