문제

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

문제 설명

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

입출력 예

n	result
15	4

---

Approach #1

n 주어지면 
start는 1부터 n까지.

ex. n이 15면
start=1부터 하나씩 쭉쭉 더해본다.
1+2+3+4+5 = 15 됐으니까 cnt++;
다음 start는 2가 된다.
2+3+4+5+6 = 20, 15보다 커지기 때문에 start 2인경우는 해당x.
3+4+5+6 = 18, 해당x
4+5+6 = 15, cnt++;

Solution #1

function solution(n) {
    let start = 1;
    //자기자신 하나만 있는경우 무조건 포함.
    let cnt = 1;
    while(start<=n){
        let sum = 0;
        for(let i=start; i<n; i++){
            if(sum===n){
                cnt++;
                break;
            }
            if(sum>n) break;
            sum+=i;
        }
        start++;
    }
    return cnt;
}

Time Complexity

O(n^2)

Space Complexity

O(1)

---

Approach #2

프로그래머스 다른사람의 풀이를 참고했는데,
n이 주어졌을때 홀수인 약수의 개수를 구하면 된다고 한다.

ex. 15
15의 홀수인 약수는 1,3,5,15

1) 약수가 1일때

• 하나의 자연수 15로 이루어져있음.

2) 약수가 3일때

• 약수가 3이므로 15 = 5 + 5 + 5 가 됨.
• 바꿔서 생각하면 4 + 5 + 6 의 연속된 자연수의 합으로 만들 수 있음.

3) 약수가 5일때

• 2)와 마찬가지로 15 = 3 + 3 + 3 + 3+ 3
• 1 + 2 + 3 + 4 + 5 의 연속된 자연수의 합으로 만들 수 있음

4) 약수가 15일때

• 1)2)3)과는 예외적으로 생각해야한다. 모든 홀수 2n+1은 n + (n+1) 의 연속된 두 수의 합으로 표현할 수 있다.
• 따라서 7 + 8 의 연속된 자연수의 합으로 만들 수 있음.

Solution #2

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

Time Complexity

O(n)

Space Complexity

O(1)

Review

수학적으로 생각하면 훨씬 효율적으로 풀리는 문제였다.
근데 이렇게 생각하려면 얼마나 공부해야할까..? ... ^.^ ;;ㅎㅎㅎㅎㅎ