[Lv.2] 숫자의 표현 (등차수열의합 / 정수론)

프로그래머스

1. 문제

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 이하의 자연수 입니다.

2. 풀이

// 등차수열의 합은 항의갯수*(초항+마지막항)/2 이다.

function solution(n) {
    var answer = 1;
    for(let i =2; i<=Math.ceil(n/2); i++){ // i는 등차수열의 갯수
        for(let j = 1; j<=Math.ceil(n/2); j++){ //j는 초항
            for(let k =2; k<=Math.ceil(n/2); k++){ // k는 마지막항
                if(j<k && k-j+1 === i){ 
                // 초항보다 마지막항이 더 크고, 항의 갯수가 마지막항-초항+1 일 경우(공차가 1인 등차수열이므로)
                    if(i*(j+k)/2 > n){ //n보다 커져버리면 break하고 다음 루프로
                        break;
                    }
                    else if(i*(j+k)/2 === n){ // n과 같으면 count하고 다음루프로
                        answer++
                        break;
                    }
                }
            }
        }
    }
    
    return answer;
}

이렇게 제출했으나 로직은 맞는데 시간복잡도가 O(n^3)이므로 시간초과로 실패.

정수론정리에 답이 있었다.

 

"주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다."

 

그래서 홀수인 약수의 개수를 세어보면

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

이렇게 통과했다.

실제 비즈니스로직 짜면서 주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수를 고민할 날이 있을까 싶긴하다.

하지만 중요한 건 수학적 지식이 비즈니스로직/알고리즘에 도움이 된다는 점이다. 

수학도 조금씩 봐야겠다.

3. 알아야할 사항

 1) "주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다."  - 정수론 정리

 2) 지금까지 '갯수'로 적었는데 '갯수'가 아니고 '개수'였다 !

한글맞춤법 제4장 제30항 '사잇소리'에 규정에 우리말과 우리말 합성어, 우리말과 한자어 합성어 사이에서 뒷말의 첫소리가 된소리로 나는 경우에 사이시옷을 받치어 적도록 규정

 

기본적인 맞춤법도 모르다니 반성해야겠다..