[2018] 수들의 합 5 (JAVA)

# 문제 설명

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

---

입력

첫 줄에 정수 N이 주어진다.

---

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

# 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int start = 1;
        int end = 1;
        int sum = 1;
        int cnt = 1;

        while (end != N) {
            if (sum == N) {
                cnt++;
                end++;
                sum = sum + end;
            }
            else if (sum > N) {
                sum = sum - start;
                start++;
            }
            else {
                end++;
                sum = sum + end;
            }
        }

        System.out.println(cnt);
    }
}

 

투 포인터(start, end)를 이용하여 문제를 풀었다.

sum은 숫자의 합, cnt는 N이 된 횟수이다.

 

end가 N이 될 때까지 반복한다.

만약 sum이 N과 같다면, cnt를 1 증가하고 end를 1 증가한다. end가 이동했으므로 sum에 end를 더해준다.

sum이 N보다 크다면, sum을 감소시켜야 하므로 start를 이동해야 한다. sum에서 현재 start를 빼주고 start를 1 증가한다.

sum이 N보다 작으면, sum을 증가시켜야 하므로 end를 이동해야 한다. end를 1 증가하고 sum에 end를 더해준다.