[Algorithms] 숫자의 표현

 

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

프로그래머스

 

프로 코테 탈락자로서 배운 것이 있다면 문제를 읽자마자 '아, 이건 ○○ 공식이네!' 하고 떠오르지 않으면 위험하다 입니다.

그런데 말입니다. 저는 이 문제를 보자마자 "DFS로 풀어볼까?" 라고 생각했습니다.

네, 그 순간 이미 탈락입니다.

 

function solution(n) {
    let answer = 0;

    function DFS(start, sum) {
        if (sum === n) {
            answer++;
            return;
        }
        if (sum > n) return;
        DFS(start + 1, sum + start + 1);
    }
    
    for (let i = 1; i <= n; i++) {
        DFS(i, i);
    }
    
    return answer;
}

 

처음엔 잘 돌아가는 줄 알았습니다.
하지만... 효율성 테스트에서 떨어졌습니다. 아주 박살이 났습니다.

왜냐고요?

내부에서 DFS는 경우에 따라 최대 O(n) 깊이까지 재귀합니다.
이걸 n번 반복하니 O(n²) 이죠.
즉, 시간 복잡도가 개판이라는 얘기입니다.ㅎ

 

문제의 핵심은 다음과 같았습니다.

연속된 자연수의 합으로 n을 표현하는 방법의 수를 구하라

 

연속된 수! 자연수! → 이건 누가 봐도 구간 합 문제
투 포인터 알고리즘입니다.

 

function solution(n) {
    let answer = 0;
    let left = 1, right = 1;
    let sum = 1;

    while (left <= n) {
        if (sum === n) {
            answer++;
            sum -= left;
            left++;
        } else if (sum < n) {
            right++;
            sum += right;
        } else {
            sum -= left;
            left++;
        }
    }

    return answer;
}

 

💡 핵심 아이디어

1. 연속된 자연수 구간 [left, right] 를 유지하면서
2. 이 구간의 합이 n과 같으면 → 정답으로 카운트
3. 합이 작으면 → right 늘리고
4. 합이 크면 → left 줄인다

🚀 이 방식이 좋은 이유

• 포인터 각각 최대 n번만 이동 → 시간 복잡도 O(n)
• 모든 수를 순회하지 않아도 됨
• 재귀? 없어요. 깔끔하고 빠름.

아니 근데  ㅅ ㅣ 발 ?

아니 근데 이거 레벨1 맞나요...? 왜 이렇게 빡빡하죠...?

 

제 뇌피셜로는 n에 Number.MAX_SAFE_INTEGER가 들어오면 무한루프 돈다는 얘기까지 생각했는데...

진짜 이유는 이게 아니었고요. 나중에 찾아보겠습니다.

찾아보니 아예 수식으로 깔끔하게 푸는 방법이 있대요.

어떤 수 n이 k개의 연속된 자연수의 합으로 표현되려면,
(n - k(k - 1)/2)가 k로 나누어 떨어져야 한다.

 

n의 홀수 약수 개수 = 정답

✔ 연속된 자연수의 합으로 n을 표현할 수 있는 경우의 수는
n의 홀수 약수 개수와 같다!

 

function solution(n) {
    let answer = 0;

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

    return answer;
}

와 진짜 초멘나사이... 이렇게 간단하다고...?

 

🧩 동작 구조

• i = 1부터 n까지의 홀수만 순회합니다 (i += 2)
• n이 i로 나누어 떨어진다면, 그 i는 n의 홀수 약수
• 이 홀수 약수 하나하나가 = 연속된 자연수의 합으로 표현하는 방법 1개
• 그래서 약수 개수 = 정답!

 

🫠 결론

네. 전 오늘도 탈락입니다.