백준 2018 - 수들의 합 5

문제

시간제한 2초

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

문제 풀이

문제의 주어진 시간은 2초 그리고 N의 최댓값이 10,000,000인 것을 생각하면 시간복잡도 알고리즘이 O(N)을 사용해야 시간제한을 초과하지 않는다고 한다.

이럴때 사용하는 알고리즘이 투 포인터 방식이다.

투 포인터 방식은

배열에서 원소를 가리키는 두 개의 포인터를 이동하면서 값을 얻어내는 방식이다.

문제의 예시 입력 1을 통해 살펴보겠다.

예시 입력 1 (N = 15)

sum = 1, count = 1

숫자 15만 뽑는 경우의 수가 있기 때문에 count를 1로 초기화

sum = 15가 될때까지 end_index를 오른쪽으로 한칸 씩 이동
end_index가 5일때 sum = 15가 나오기 때문에 count를 1 증가시켜준다.
그 다음 end_index를 오른쪽으로 한칸 이동 해준다.
하지만 sum은 21이 되기 때문에 더이상 end_index를 더해주면 sum보다 높은 숫자가 나오기 때문에 이 때는 start_index를 오른쪽으로 한칸 씩 이동 시킨다. 그리고 sum에도 start_index를 오른쪽으로 이동하기 전에 포인터에 있는 값을 빼준다.

그러다가 start_index가 4일때 sum = 15 (4 + 5 + 6)이 나오기 때문에 count를 1 증가시켜준다.

이러한 방법으로 문제를 접근해보면서 코드를 적용시켜보겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class 수들의합5 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int start_index = 1;
        int end_index = 1;
        int sum = 1;
        int count = 1;

        while(end_index != N) {
            if(sum == N){
                count++;
                end_index++;
                sum += end_index;
            }else if(sum > N){
                sum -= start_index;
                start_index++;
            }else { // sum < N
                end_index++;
                sum += end_index;
            }
        }

        System.out.println(count);

    }

}

회고

Do it! 알고리즘 코딩 테스트 책을 참고해서 문제를 풀었다. 따로 책을 보지 않았다면 시간초과가 나왔을 것이다. 계속 비슷한 유형의 다른 문제도 같이 풀어봐야 겠다는 다짐을 하게 된다.