[프로그래머스] 숫자의 표현 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　이 문제는 자연수 n을 연속한 자연수들의 합으로 표현하는 방법의 수를 찾는 문제다. n이 주어지면, 한 개 이상의 연속된 자연수의 합으로 n을 표현하는 방법의 수를 찾아야 한다. 풀이는 다음 두 가지 방법으로 접근하여 보았다.

 

1. 투 포인터 알고리즘: 두 개의 포인터를 이용하여 연속된 수들의 합을 관리. start와 end 두 포인터를 동시에 이동시키면서 그 사이의 합과 n이 어떻게 비교되는지를 확인. 합이 n보다 작다면 end를 증가시키고, n과 같다면 카운트를 증가시킨 후 start를 증가시키고, n보다 크다면 start를 증가.
2. 브루트 포스 알고리즘: 가능한 모든 연속된 수열을 검사하며 그 합이 n인 경우를 찾음.

 

　두 방법 모두 적절히 활용한다면 문제를 해결할 순 있지만, 시간 복잡도 측면에서 투 포인트 알고리즘이 O(n), 브루트 포스 알고리즘이 O(n^2)이므로 투 포인터 알고리즘이 더 효율적인 방법이라고 할 수 있다.

---

풀이 (1) 브루트 포스 알고리즘

using namespace std;

int solution(int n) 
{
    int cnt = 0; 

    for (int i = 1; i <= n; ++i)
    {
        int sum = i;

        for (int j = i + 1; j <= n; ++j)
        {
            sum += j;

            if (sum == n)
            {
                cnt++;
                break;
            }

            else if(sum > n)
                break; 
        }
    }

    cnt++; 
    return cnt;
}

---

풀이 (2) 투 포인터 알고리즘

int solution(int n) 
{
    int answer = 0;
    int start = 1, end = 1, sum = 1;  

    while(start <= end) 
    {
        if(sum < n) 
        {
            end++;
            sum += end;
        }
        
        else if(sum == n) 
        {
            answer++;
            start++;
            
            if(start <= end) 
            	sum -= start - 1;
        }
        
        else 
        {  
            sum -= start;
            start++;
        }
    }
    
    return answer;
}