[Algorithms] 연속된 자연수의 합 (프로그래머스-숫자의표현)

 

프로그래머스 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 이하의 자연수 입니다.

 

 

---

코드

function solution(n) {

    let answer = 0;
    let sum = 1;
    let i = 1;
    
    while(sum <= n) {
        if ((n - sum) % i === 0 ) {
            answer++;
        }
        i++;
        sum += i;
    }
    
    return answer;
}

 

풀이

코드자체는 어렵지 않았지만 수학적풀이가 필요한 문제였던 것 같다.

연속된 자연수들의 합으로 n을 만들 수 있는 가지 수를 구하는 문제인데 규칙성을 발견하지 못했었다 ㅜ

 

일단 해결한 방법은 아래와 같다.

 

• 구해야 하는 수 N
• 더할 자연수들의 개수 i
• 1부터 i까지의 합 sum

세가지를 이용해서 만든 코드이다.

 

원리는...

만약 연속되는 자연수 2개로 15를 만든다고 가정해보자.

 

• 두 개의 자연수를 ㅁ, ㅁ라고 했을 때 연속되는 자연수여야 하기 때문에 두 수의 차이는 1 이다.
• ㅁ,ㅁ의 자리에 1,2를 대입해 15에서 (1+2)를 빼주면 15-3 = 12. 자연수는 두개임으로 12/2를 하면 6이 나온다.
• 따라서 두 개의 자연수는 6(1+2) => 7+8 인 것이다.

 

한 마디로 정의를 하면 

 

💡

(N - sum) % i === 0

 

구해야 하는 수에서 더할 자연수들의 개수만큼 더한 sum을 뺀 값을 자연수들의 개수로 나눴을 때 나머지가 남지 않는다면,

i개의 연속되는 자연수로 N을 구할 수 있다는 뜻이다.