C++ / 프로그래머스 / 숫자의 표현

문제

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

프로그래머스

문제풀이

투 포인터를 이용해 풀었다.

시작 숫자를 s, 끝부분 숫자를 e로 두었다.

n / 2 +1 이상의 수로는 연속된 수로 표현할 수 없기 때문에 e의 최대 범위를 n / 2 + 1로 잡았다. 

투 포인터 원리를 이용하여 값이 작하면 e를 늘려 sum에 더하고,

값이 크면 sum에서 s를 빼고 s를 한칸 오른쪽(+1)으로 옮겼다.

문제를 보면 숫자 하나로 나타낸 값도 포함이므로 (자기자신),

n / 2 + 1 범위에 안 겹치게 n이 2를 초과할때만 answer에 1을 더해주었다.

 

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer(0), s(1), e(0), sum(0);

    if (n > 2) {
        answer++;
    }

    while (e <= n / 2 + 1) {
        if (sum < n) {
            ++e;
            sum += e;
        }
        else if (sum >= n) {
            sum -= s;
            s++;
        }
        if (sum == n) {
            answer++;
        }
    }
    return answer;
}