[JAVA] 백준 (실버5) 2018번 수들의 합 5

링크

https://www.acmicpc.net/problem/2018

---

문제 설명

정답률 49.017%
어떠한 자연수 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이 주어진다.

15

---

출력 예제

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

4

---

풀이

N의 최대값은 $10^7$으로 엄청 크다. 일일이 시작 인덱스만을 갱신시켜 나가서 경우의 수를 따지면 시간 초과가 날 것이다. 그래서 두 개의 인덱스를 이용하는 투 포인터를 이용한다.

시작 인덱스와 끝 인덱스를 1로 잡아 끝 인덱스가 N이 될 때까지 반복한다.
인덱스를 갱신시킬 때는 다음과 같이 구분한다.

• 합이 N보다 작을 때
• 합이 N과 같을 때
• 합이 N보다 클 때

처음에는 합이 N보다 작으니 end를 한칸 씩 증가시키며 sum에 더해간다.

if (sum < N) {
    end++;
    sum += end;
}

그러다가 sum이 N이 되는 순간이 오면 정답으로 카운트한다. 그리고 end를 다시 증가시킨다. 당연히 sum도 end만큼 더한다.

else if (sum == N) {
    count++;
    end++;
    sum += end;
}

그럼 sum은 N보다 커질텐데 이때 start를 갱신시키기 위해 sum에서 현재 start를 빼주고 새로 갱신시킨다.

else if (sum > N) {
    sum -= start;
    start++;
}

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int count = 1;
        int start = 1;
        int end = 1;
        int sum = 1;

        while (end < N) {

            if (sum < N) {
                end++;
                sum += end;
            } else if (sum == N) {
                count++;
                end++;
                sum += end;
            } else if (sum > N) {
                sum -= start;
                start++;
            }
        }

        System.out.println(count);
    }
}