프로그래머스 숫자의 표현 [Lv. 2]

프로그래머스

숫자를 입력받을 때, 연속된 숫자의 합으로 입력받은 수를 만들 수 있는 경우의 수를 찾아주세요.

 

풀이 방법

연속된 수를 찾는 것이기 때문에 수열의 범위를 조절하는 투 포인터 알고리즘을 이용할 수 있겠습니다.

 

N이 15일 때, 1부터 시작하여 모든 수를 합해줍니다.

[1, 2, 3, 4, 5] = 15

수의 합이 15가 나온다면 answer을 하나 늘려주고 다음 수를 추가합니다.

 

[1, 2, 3, 4, 5, 6] = 21

수의 합이 15보다 크기 때문에 15보다 작거나 같은 수가 될 때 까지 앞의 수를 제거합니다.

 

[4, 5, 6] = 15

수의 합이 15이기 때문에 answer을 하나 늘려주고 다음 수를 추가합니다.

 

[4, 5, 6, 7] = 22

수의 합이 15보다 크기 때문에 15보다 작거나 같은 수가 될 때 까지 앞의 수를 제거합니다.

 

[6, 7] = 13

 

수의 합이 15보다 작기 때문에 다음 수를 추가합니다.

 

[6, 7, 8] = 21

수의 합이 15보다 크기 때문에 앞의 수를 제거합니다.

 

[7, 8] = 15

수의 합이 15이기 때문에 answer을 늘려주고 다음 수를 추가합니다.

 

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

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

    queue<int> q;
    int total = 0;
    int num = 1;
    
    while (num <= n+1)
    {
        if (total >= n)
        {
            total -= q.front();
            q.pop();
        }
        else
        {
            total += num;
            q.push(num++);
        }
        
        
        if (total == n)
            answer++;
    }  
    return answer;
}