프로그래머스 - 숫자의 표현

문제내용

10,000 이하의 자연수 n을 연속된 자연수로 표현하는 경우의 수를 찾는 문제입니다

 

문제출처

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

프로그래머스

 

 

해결방법

이 문제는 두가지 방법으로 해결했습니다

 

해결방법 1

가장 단순한 방법인 1부터 n까지 순회하며 n과 같아지는 수를 찾아 세는 방법이었습니다.

시간복잡도는 O(n) 입니다.

 

 

해결방법 2

n을 연속된 자연수의 합으로 나타내는 방법의 수는 n의 홀수 약수 개수와 같았습니다.

 

예를 들어서 문제의 예시로 나왔던 n = 15의 약수는

1, 3, 5, 15

 

전부 홀수이고 4개입니다

실제로 15를 연속된 자연수의 합으로 표현하는 방법도 4개였습니다

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

 

연속된 자연수 k를 더한다고 생각해보겠습니다

예를 들어서 3개를 더하면 

4, 5, 6

 

가운데 숫자는 5이고

(5 - 1) + 5 + (5 + 1)
= 5 × 3
= 15

 

이 됩니다

 

5개라면 

1 + 2 + 3 + 4 + 5

 

가운데가 3이므로 

3 × 5 = 15

 

이 됩니다

 

아래와 같은 방식으로 홀수 개의 연속된 숫자의 합은

가운데 숫자 × 숫자의 개수

 

위와 같이 구할 수 있었습니다.

 

최종코드

 

해결방법1

function solution(n) {
    let answer = 0;

    for (let start = 1; start <= n; start++) {
        let sum = 0;

        for (let num = start; num <= n; num++) {
            sum += num;

            if (sum === n) {
                answer++;
                break;
            }

            if (sum > n) {
                break;
            }
        }
    }

    return answer;
}

 

 

해결방법2

function solution(n) {
    let answer = 0;

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

    return answer;
}

 

 

참고자료