프로그래머스, 자바스크립트) 숫자의 표현

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

풀이

문제 접근을 생각해보면...1+2+3+4 연속된 자연수를 가져야 되니 일단 반복문을 돌려서 숫자를 준비한다.

그러면 1+2+3 ... , 2+3+4..., 이런식으로 처음 시작되는 숫자를 기준으로 더한 값을 구할 수 있다. 

n이 되는 연속 합을 찾기 위해 n이 되면 answer를 증가시키고 쓸데없는 반복이 없도록  n 이상이면 break

function solution(n) {
  let answer = 0;

  for (let i = 1; i <= n; i++) {
    //숫자 나열
    let sum = 0;
    for (let j = i; j <= n; j++) {
      //해당 숫자부터 n까지의 합
      sum += j;
      if (sum === n) answer++; //합이 n이면 answer 증가
      if (sum >= 15) break; //합이 15이상이면 탈출
    }
  }
  return answer;
}

다른 풀이

수학적 접근, 연속된 자연수의 합이 n이 되려면, 연속된 숫자의 합 공식을 이용할 수 있다.

(start+start+length−1)×length/2=n. 
start는 연속된 자연수의 시작점, length는 연속된 자연수의 개수

• 가능한 모든 length 값을 검사한다.
• length * (length + 1) / 2 <= n 조건은 length가 지나치게 커져서 n을 넘지 않도록 제한한다.
• (n - (length * (length - 1)) / 2) % length === 0 조건은 n에서 length의 합을 뺀 후 나머지가 0이 되는지 확인하여, 해당 length가 유효한 연속 합을 만드는지 검사한다. 나머지가 0이면 유효한 연속합이므로 answer를 증가

function solution(n) {
  let answer = 0;
  
  for (let length = 1; length * (length + 1) / 2 <= n; length++) {
    // 연속된 숫자의 개수에 따라 시작점을 구함
    if ((n - (length * (length - 1)) / 2) % length === 0) {
      answer++;
    }
  }

  return answer;
}