[Lv 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를 완성해주세요.

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

🙋‍♀️ 나의 풀이 1

function solution(n) {
  let answer = 1;
  let acc = 0;
  for (let i = 1; i <= n / 2; i++) {
    for (let j = i; j <= n; j++) {
      acc += j;
      if (acc > n) break;
      if (acc == n) {
        answer++;
        acc = 0;
        break;
      }
    }
    acc = 0;
  }
  return answer;
}

처음에 for문을 돌려 연속된 수의 합을 구했는데 정확성 테스트는 통과했지만 효율성 테스트에서 모두 막혔습니다.

어떻게든 넘어가려고 if문에 i 조건까지 수정했는데 통과할 수 없어 풀이 과정 자체에 대해 다시 생각했습니다.

🙋‍♀️ 나의 풀이 2

function solution(n) {
  let answer = 0;
  for (let i = 1; i <= n; i++) {
    if (n % i === 0 && i % 2 === 1) answer++;
  }
  return answer;
}

연속된 수의 합을 구하는 방법을 찾던 중 다음과 같은 방법을 찾았습니다.

자연수의 소수 중 홀수의 개수는 연속된 자연수의 합이 나올 수 있는 개수와 같다.

예를 들어,

15의 약수는 [1, 3, 5, 15]입니다.

• 1의 경우, 연속하는 1개의 자연수로 표현 가능 => 15
• 3의 경우, 연속하는 3개의 자연수로 표현 가능 => 3+4+5
• 5의 경우, 연속하는 5개의 자연수로 표현 가능 => 1+2+3+4+5
• 15의 경우, 모든 홀수는 n과 n+1로 표현가능 => 7+8

이 풀이에서는 공식을 사용했기 때문에 for문이 한번만 돌아가 효율성 테스트를 모두 통과할 수 있었습니다.

다른 문제보다 수학적 지식이 요구되었던 문제였던것 같은데 정답률(73%)이 높네요.

원래 수학은 졸업하면 까먹는건데…