• 문제출저 : https://school.programmers.co.kr/learn/courses/30/lessons/12924

BretueForce로 접근하면 효율성 문제를 통과하지 못한다. (n/2)개를 순회한다 하여도 1, 1+2, 1+2+3, ...., 2, 2+3, 2+3+4, ... k, k+1, k+2,.... 의 경우를 계산하여야 하므로 O(n^2)가 나올 것이다.
또한 위의 방법은 다른 블로그에 이미 많이 존재하기 때문에 넘어가도록 함.

수학 - 연속된 수의 합

풀이

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

연속되는 자연수의 개수를 i라 하자.

• i=5, 15/5 = 3, 3*5 = 15, 3+3+3+3+3 = 15 = (3-2) + (3-1) + 3 + (3+1) + (3+2) 로 볼 수 있다.
• i=3, 15/3 = 5, 5*3 = 15, 5+5+5 = 15 = (5-1) + 5 + (5+1)
• i=2, 15/2 = 7.5, 7.5*2 = 15, 7.5+7.5 = 15 = (7.5 - 0.5) + (7.5+0.5)
• i=1, 15/1 = 15, 15*1 = 15

n을 i로 나눴을 때 나오는 중간값 mid를 바탕으로 mid에 연속한 i개의 자연수들의 합이 n과 같으면 n을 i개의 자연수로 표현할 수 있다.

i가 홀수일 때

• mid값은 자연수가 나와야 하므로 n%i=0 이다.
• i >= 1이므로 k>=0이고, 연속된 자연수의 개수는 k+k+1이므로 i=2k+1이다.
• '자연수'이므로 최솟값인 mid-k >= 0 이어야 한다.
• (2k+1)*mid = n

i가 짝수일 때

• mid값에 가장 근사한 두 값이 mid와 같은 거리에 있어야 한다. 그러므로 n/i 는 자연수.5의 값이어야한다.
• mid에서 올림한 값을 t, 내림한 값을 b라 하자. t+b = 2*mid
• i는 적어도 2개이므로 i>=2, k>=0, i=2k+2
• 자연수이므로 최솟값인 b-k > 0
• (k+1)2mid = n

코드

function solution(n) {
  if (n === 1) return 1; // 15번 n === 1일 때

  let count = 0;

  for (let i = 1; i <= Math.ceil(n / 2); i += 2) {
    const mid = n / i;
    const k = (i - 1) / 2;

    if (n % i !== 0) continue;
    if (mid - k <= 0) continue;

    if ((2 * k + 1) * mid === n) {
      count += 1;
    }
  }

  for (let i = 2; i <= Math.ceil(n / 2); i += 2) {
    const mid = n / i;
    const k = (i - 2) / 2;

    if ((n * 10) / i !== Math.floor(n / i) * 10 + 5) continue;
    if (Math.floor(n / i) - k <= 0) continue;

    if ((k + 1) * 2 * mid === n) {
      count += 1;
    }
  }

  return count;
}

• i가 짝수일 때, mid가 정확히 자연수 + 1/2의 값임을 보장할 수 있도록 10을 곱한 후 2로 나눈 값과 비교하였다. (소수 계산 오류 방어)
• n === 3 을 넣고 돌렸을 경우, 짝수의 경우 2 <= 1.5 로 시작하므로 실행되지 않는다. Math.ceil을 넣어줘야 문제 16번을 통과할 수 있다.
• O(n)