Programmers / Level 2 / 숫자의 표현 / JS

< 문제 바로가기 >

프로그래머스

 

function solution(n) {
    let result = 0;

    for(let i=1; i<=n; i+=1) {
        if(n % i === 0 && i % 2 === 1) {
            result += 1;
        }
    }

    return result;
}

---

위의 코드같이 하지 않고 다음과 같이 2중 반복문으로 쉽게 풀 수 있는 문제이다. (cpp)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    for(int i=1; i<=n; i++) {
        int sum = 0;
        for(int j=i; j<=n; j++) {
            sum += j;
            if(sum >= n) break;
        }
        if(sum == n) answer++;
    }
    
    return answer;
}

 

하지만 맨 위에 있는 첫번째 풀이로 한다면 더욱 빠른 시간으로 해결할 수 있다.

일단 코드 풀이를 해보자. (수학적인 개념이 들어간다...)

 

우리는 n이하인 초항인 a부터 연속적인 숫자인 k개의 합으로 n을 만들어야 한다.

이것을 수식으로 나타내면 다음과 같다.

 

a + (a + 1) + (a + 2) + ... + (a + k - 1) = n

 

여기서 우리는 1부터 n까지의 합을 구하는 공식을 떠올리면 된다.

1부터 n까지의 합을 구하는 공식은 n * (n + 1) / 2 로 어디선가 본 적이 있을법한 수식이다.

 

위 수식의 각 항은 무엇을 나타낼까?

말로 풀어서 쓴다면 다음과 같다.

 

항의 개수 * (초항 + 마지막 항) / 2

 

우리가 수식으로만 외워서 그렇지, 사실 위 공식이 도출되는 과정은 매우 간단하다.

예를 들어 1부터 10까지 더한다고 생각해보자.

 

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

 

위 숫자에서 같은 색깔끼리 더하면 11이되고, 그 11이 5개가 있다.

이것을 다시 나타내보면,

 

(첫 번째 항 + 마지막 항) = 11,

11을 이루는 쌍의 개수 = (항의 개수 / 2) = 5

위 둘을 곱하면 55.

 

위와 같이 공식이 도출된다.

 

우리는 n이하인 초항인 a부터 연속적인 숫자인 k개의 합으로 n을 만들어야 한다.

항의 개수 * (초항 + 마지막 항) / 2

 

위에서 언급했던 두 문장을 그대로 가져왔다. 이것을 이제 공식에 도입해보자.

 

항의 개수 = k

초항 = a

마지막 항 = a + k - 1

 

따라서, k * (a + (a + k - 1)) / 2 = n 이 된다.

 

좌변을 a로 정리해보면,

a = n / k - (k - 1) / 2 가 된다.

 

여기서 하나 더 생각해야 할 것이 있다.

좌변에 있는 a는 초항이다. 초항은 항상 자연수이다.

따라서 우변에 있는 식도 자연수가 되야할 것이다.

그렇다면, 우변에 있는 두개의 항인 n / k와 (k - 1) / 2 모두가 자연수가 되어야 자연수인 결과값이 나올 것이다.

 

• n / k가 자연수가 되려면 k는 n의 약수여야 한다.
  다시 말하면, 항의 개수는 n의 약수여야 한다.
• (k - 1) / 2가 자연수가 되려면 k - 1은 짝수여야 한다.
  다시 정리하면 k, 항의 개수는 홀수여야 한다.

 

우리가 문제에서 구하려는 것은, n을 이루는 연속된 k개의 숫자의 합의 개수이다.

따라서 위 조건 두개를 모두 만족하는 k를 모두 구해서 카운팅해주면 된다.