또 수학이야

-컴공에서 수학만 4년 수강한 박감자-

문제 설명

문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12924

문제 후기

연속되는 수의 합이 주어진 n이 되는 경우의 수를 구하는 문제로, 구현은 어렵지 않았으나, 시간초과가 많이 떠서 조금 애먹은 문제이다ㅠㅠ

풀이 과정

완전탐색

처음에 생각해본 방법

1. 1에서부터 n/2까지의 수를 i로 순회한다.
2. i로부터 연속되는 수의 합을 n과 비교하여 같으면 경우의 수에 1을 더한다
3. n이 홀수인 경우 n/2의 값의 floor와 ceiling을 더하여 n이 되므로 이 경우도 경우의 수에 1을 더한다.
4. 모든 n은 n이라는 자연수의 합이되기도 하므로 answer (경우의 수)를 1에서 시작한다.

n/2로 설정한 이유는 순회하는 시간 복잡도를 줄이고 싶기도 했고, 무엇보다 홀수인 경우 (n/2 - 1) + (n/2 + 1) = n이 늘 참이다. 짝수는 n/2에서 n/2 + 1을 더하는 순간 n을 초과하기때문에 앞의 n/2 부분의 경우만 고려를 해도 문제가 없다고 판단하였다.

위의 방법을 따라 작성한 코드는 아래와 같다.

function solution(n) {
    let answer = 1;
    
    for (let i = 1; i < n/2; i++) {
        // 연속된 수의 합
        let sum = 0;
        // i 부터 연속된 숫자의 합이 n과 같은지 확인하는 작업
        let start = i;
        while (sum < n) {
            sum += start++;
        }
        
        // 더한 값이 n일때
        if (sum === n) {
            answer += 1;
        } else if (i + (i+1) === n) {
            // i가 n의 Math.floor(n/2)인 경우
            // i+1을 더하면 n이다.
            answer += 1;
        }
    }
    
    return answer;
}

시간초과로 처참히 실패했다

2안 : 수학적 접근 - $\sum_{k=1}^n k$

사실 방법이 생각이 안나기도 해서 구글링을 조금 해본 결과 시그마 k를 활용할 수 있다고 한 글을 보고 작성해본 코드이다.

$\sum_{k=1}^n k = \frac{k(k-1)}{2}$ 라는 공식을 대학교 이후 본적이 없었지만...

위의 식은 1에서부터 n의 합을 계산한 결과이고 우리의 문제에서는 1이 아닌 어디서든 시작할 수 있기에 식의 변형이 필요했다.

따라서 더 찾아본 결과 임의의 x에서 시작하여 k개의 합을 구하는 공식은 아래와 같다

예를 들어 4에서 시작하는 연속되는 자연수 3개의 합을 구할때

구하고자 하는 합이 n이므로 식을 x에 대하여 새로 쓴다면

여기서 x는 임의의 자연수이기 때문에 $n - \frac{k(k-1)}{2}$는 $k$로 나누어 떨어져야 하며 0이상이어야 한다 $n - \frac{k(k-1)}{2} > 0$ -> $n > \frac{k(k-1)}{2}$

위의 조건들과 k개를 늘려서 확인하는 방식의 코드를 작성하면 아래와 같다

function solution(n) {
    let answer = 0;

    // n이 되는 k개가 존재하는 체크
    // 예를 들어 15는 연속되는 1, 2, 3, 5개의 자연수로 더해질 수 있지만
    // 자연수 4개로 만들 수 없다
    for (let k = 1; k * (k - 1) / 2 < n; k++) {
        // x = (n - (k * (k - 1)) / 2) / k 정수인 경우만!
        if ((n - (k * (k - 1)) / 2) % k === 0) {
            answer++;
        }
    }

    return answer;
}

다행히도 모두 통과하였다!

추가안

이런 글이 있기에 https://school.programmers.co.kr/questions/36800
홀수인 약수의 개수가 정답입니다. ????
설명도 한 줄이길래 JS로 다시 썼는데

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

    return answer;
}

이왜진...
정확성, 효율성 모두 통과하였다.
풀이는 https://velog.io/@feyouhyun0957/프로그래머스-숫자의-표현-JS 에서 잘 설명해주고 있다

마치며...

완전탐색을 하면 시간초과가 될걸 알면서도 하는 이유는
생각이 안 나서입니다.

그래서 앞으로 알고리즘 풀때 완전탐색이 아닌 다른 방법을 우선적으로 브레인 스토밍하는 습관이 필요할것 같다