[알고리즘]프로그래머스 12924번 - 숫자의 표현

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

프로그래머스 12924번 - https://programmers.co.kr/learn/courses/30/lessons/12924

 

요구사항

1. 자연수 n을 연속한 자연수의 합으로 표현하는 방법의 수를 반환하라.

 

요구사항 분석 및  풀이과정

1. 매번 연속한 자연수의 합을 구하는 건 비효율적이므로, 1부터 n까지의 합을 미리 구해둔다.

 

dp[i] = 1부터 i까지의 합

dp[i] = dp[i-1] + i ( 1 <= i <= n ), dp[0] = 0

 

2. i부터 j까지의 자연수의 합은 dp[j] - dp[i-1] 이다. (단, i <= j )

 

dp[j] = 1 + ... + j, dp[i-1] = 1 + ... + i - 1

dp[j] - dp[i-1] = i + ... + j

 

3. 만약 i부터 j까지의 자연수의 합이 n보다 작다면, 더해지는 수인 dp[j]가 커져야 하므로 j를 증가시킨다.

4. 만약 크다면 빼는 수인 dp[i-1]가 커져야 하므로 i를 증가시킨다.

5. 만약 같다면, 더해지는 수는 커지고, 빼는 수는 작아져야하므로 j와 i 모두 키운다. 

 

이러한 방법이 가능한 이유는 dp[i]는 증가수열이기 때문이다. 

투 포인터의 핵심이다.

 

소스코드 작성

import java.util.Arrays;

class Solution {

    public int solution(int n) {
        int[] dp = new int[n+1];
        
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + i;
        }
        
        int result = 0;
        int left = 0, right = 1;
        
        while(right <= n) {
            int v = dp[right] - dp[left];
            if (v == n) {
                left++;
                right--;
                result++;
            } else if (v < n) {
                right++;
            } else {
                left++;
            }
        }
        
        return result;
    }
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

자연수 n을 n과 같거나 작은 자연수의 연속적인 합으로 구하는 방법의 수는 자연수 n의 홀수 약수의 개수와 같다는 정수론 정리가 있다. 알면 도움이 될 수 있겠지만 무조건 알아야하는 건 아니다. 나 또한 그 방법으로 풀지 못했고, 일반적으로 떠올리기 힘들다고 생각한다.