2024.02.04 알고리즘

숫자의 표현 (lv 2)

 

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

프로그래머스

 

 

시도 1 - 효율성 실패

배열로 완전 탐색 시도

function solution(n) {
    let answer = 1; // 자기 자신
    const numberList = [Math.round(n / 2), Math.round(n / 2) - 1];
    
    while (!numberList.includes(0)) {
        const sum = numberList.reduce((a, c) => a + c, 0);

        if (sum === n) answer++;
        
        if (sum >= n) 
        	numberList.shift();
        
        if (sum <= n) 
        	numberList.push(numberList[numberList.length - 1] - 1); 
        
    }
    return answer;
}

시도 2 - 효율성 실패

투포인터로 완전 탐색 시도

시도 1에선 효율성 1개에서 실패했으나,,,, 여기선 효율성 3개 실패...

function solution(n) {
    let answer = 1; // 자기 자신
    let pointer1 = 0;
    let pointer2 = 2;
    const numberList = Array.from(
        {length: Math.round(n / 2)}, (_, i) => Math.round(n / 2) - i);
    
    while (pointer2 <= numberList.length) {
        const sum = numberList.slice(pointer1, pointer2)
            .reduce((a, c) => a + c, 0);
        
        if (sum === n) answer++;
        if (sum <= n) pointer2++;
        if (sum >= n) pointer1++;
    }
    return answer;
}

 

시도 3

아니...

시도 1과 시도 2 둘에서 조금이라도 효율성을 높일 수 있는 곳이 있나 해서

이것저것 테스트해보다가...

시도 1과 똑같은 코드로 테스트를 통과해버렸네

 

다른 풀이방법

수학적으로 접근하면 냅다 쉽게 풀이할 수 있다고 한다.

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

 

정수론에 따르면, 
주어진 자연수를 연속된 자연수의 합으로 펴현하는 방법의 수는
주어진 수의 홀수 약수의 개수와 같다라는 정리가 있다고 한다.

 

몇 가지 예시를 들면 쉽게 이해할 수 있다.

 

15의 경우 약수가 1, 3, 5, 15 로 구성되어 있다.

3 X 5 = 15

3이 5개면 3 + 3 + 3 + 3 + 3 = 15라 표현할 수 있다

이를 또 다르게 표현하면
3 + 3 + 3 + 3 + 3 은 3 + 2 + 3 + 4 + 3 와 같고
3 + 2 + 3 + 4 + 3 은 1 + 2 + 3 + 4 + 5 와 같다


5 X 3 = 15

-> 5 + 5 + 5 = 4 + 5 + 6 = 15

1 X 15 = 15
1 + 1 + ... 1 = 반으로 잘라 7 + 8 = 15 로 만들 수 있다!

15 X 1 = 15 = 15
-> 바로 자기 자신!

 

16의 경우 약수는 1, 4, 16 이다.

4 X 4 = 4 + 4 + 4 + 4

4 + 4 + 4 + 4 = 3 + 4 + 5 + 4

마지막 숫자 4가 대칭될 수가 남아있지 않다 

약수 중 짝수의 경우
홀수처럼 대칭되게 숫자를 만드 수 없기 때문에 
해당 자연수를 연속된 자연수의 합으로 만들지 못한다는 결론을 얻을 수 있다!

그래서 16의 경우, 약수 중 홀수가 1 밖에 없으므로

연속된 자연수의 합은
16 = 16 
단 하나의 식만 성립함을 알 수 있다

 

결론

수학의 세계는 넓고 알아갈수록 보이는게 많다!