[투 포인터] 연속된 자연수의 합 구하기

목차

1. 풀이

(1) 문제

연속된 자연수의 합 구하기, 백준 2018 : https://www.acmicpc.net/problem/2018

 

문제 핵심

- 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합

- 연속된 자연수 합의 가지 수

 

(2) 풀이

- N의 범위가 매우 크기 때문에 O(n) 이하의 시간복잡도를 가진 알고리즘을 사용해야 한다.

 

* 투 포인터 *

- 투 포인터는 말 그대로 두 개의 포인터를 활용한 알고리즘이다.

- 이 문제에서는 시작 인덱스와 종료 인덱스 두개의 포인터를 사용한다.

- O(n) 시간복잡도를 가진다.

 

(3) 문제 적용 예시

변수 선언 및 초기화

- 입력받은 값이 5라고 가정한다.

- 연속된 자연수의 합은 sum, 가지수는 count 변수로 선언한다.

- start_index 와 end_index 둘다 1에 포인터를 지정한다.

- 투 포인터 둘다 1을 가리키므로 sum = 1로 초기화 한다.

- end_index가 입력받은 값(예시에선 숫자 5)을 가리키면 반복문이 끝나므로 count = 1 로 초기화

 

투 포인터 이동 원칙 적용

* (sum < N) 연속된 합이 입력 값보다 작을 경우
    end_index++;
    sum = sum + end_index;
    
* (sum > N), 연속된 합이 입력 값보다 클 경우
    sum = sum - start_index;
    start_index;
    
* (sum == N), 연속된 합이 입력 값과 같을 경우
    end_index++;
    sum = sum + end_index;
    count++;

 

2+3 = 5 일때

 

• sum은 1이므로(처음 sum은 1로 초기화된 상태) 입력된 값 5 보다 작으므로 end_index를 오른쪽으로 옮겨 주고 더해준다. sum = 1 + 2 = 3
• sum = 3 은 5 보다 작으므로 end_index를 오른쪽으로 옮겨주고 더해준다. sum = 3 + 3 = 6
• sum = 6 은 5 보다 크므로 sum - start_index 후 start_index를 오른쪽으로 옮겨준다. sum = 6 - 1 = 5
• sum = 5 이므로 count를 1 증가 시켜주고 end_index 오른쪽으로 옮겨주고 더해준다. 
• 이 과정을 end_index가 5에 도착할 때까지 반복해준다.

2. 정답

import java.util.Scanner;

public class p2018_연속된자연수의합구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int sum = 1;
        int start = 1;
        int end = 1;
        int count = 1;

        while (end != N) {
            if (sum == N) {
                count++;
                end++;
                sum += end;
            } else if (sum > N) {
                sum -= start;
                start++;
            } else {
                end++;
                sum += end;
            }
        }
        System.out.println(count);

        sc.close();
    }
}

 

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)