[lv2] 숫자의 표현

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

 

다른 사람 풀이에 좀 더 수학적인? 정수론을 이용한 풀이가 있었다.

나는 누적합으로 풀고 투 포인터도 될 것 같아서 다시 풀었다.

 

투 포인터 풀이

합이 n인 연속된 자연수 (k + k+1 ... k+m) 수열이 존재한다면, k 부터 시작하는 경우는 유일하다.

e.g. 1+2+3+4+5 = 15라면, 15를 만드는 수열 중 k = 1부터 시작하는 경우는 1가지 뿐이다.

 

 

1. sum > n 라면,

=> 더 이상 수를 더해도 정답인 경우는 없다. st 값을 빼준다.

 

2. sum = n 라면,

=> 더 이상 수를 더해도 정답인 경우는 없다. answer++하고 st 값을 빼준다.

 

3. sum < n 라면,

=> 연속된 수를 더했을 때 정답일 수 있다. ed를 더해준다.

 

 

이건 누적합 풀이

class Solution {
    public int solution(int n) {
        
        int answer = 0;
        int[] sum = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            sum[i] = sum[i-1] + i;
        }
        
        for(int i=n; i>0; i--) {
            int num = sum[i];
            
            if(num == n) {
                answer++;
                continue;
            }
            
            for(int j=i-1; j>0; j--) {
                
                int diff = num - sum[j];
                if(diff == n) {
                    answer++;
                    break;
                }
                
                if(diff > n)
                    break;
            }
        }
        
        return answer;
    }
}

 

 

class Solution {
    public int solution(int n) {

        int answer = 0;

        // n은 10,000 이하의 자연수 입니다.
        int st = 1;
        int ed = 2;
        int sum = 1;

        while(ed <= n + 1) {

            if(sum > n) {
                sum -= st;
                st++;
            }

            else if(sum == n) {
                answer++;
                sum -= st;
                st++;
            }
            else if(sum < n) {
                sum += ed;
                ed++;
            }
        }

        return answer;
    }
}