[백준, 2018] 수들의 합

어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 구하는 문제

 

연속된 수의 조합이고 N의 범위가 크기 때문에 투 포인터(lt, rt)를 사용해서 조합의 합이 N보다 작으면 rt를 증가, N보다 크면 lt를 증가 시키면서 이동한다.

 

곧바로 떠오르는 고려할 점은 어디까지 수를 체크 할 것이냐인데 최소한의 연속된 수로 나타낼 수 있는 경우는 N의 절반이 될 것이다.

 

연속된 숫자가 1개인 경우도 포함되기 때문에 자기 자신도 포함하면 기본값은 1이 될 것

 

int N = Integer.parseInt(br.readLine());
int end = N / 2;
int count = 1;
int lt = 1;
int rt = 2;
int sum = lt + rt;

while (lt <= end) {
    if (sum > N) {
        sum -= lt;
        ++lt;
    }
    if (sum == N && rt != N) {
        ++count;
    }
    if (sum <= N) {
        ++rt;
        sum += rt;
    }
}