문제

어떠한 자연수 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
백준 2018 상세보기

분석

연속된 자연수의 합이 N이 되는 경우의 수를 구하는 문제이다. 이런 경우 투 포인터 알고리즘을 활용할 수 있다.
작성할 코드를 단계별로 생각해 보자.

1. 입력받은 자연수를 N에 저장하고, 코드에서 사용할 변수인 투 포인터(start, end), 합계(sum) 그리고 경우의 수(count)를 초기화한다.
   이때, count는 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 계산하여 1로 초기화한다.
   start = 1, end = 1, sum = 1, count = 1
   
2. 포인터가 이동할 때마다 현재의 총합(sum)과 N을 비교하면서 연속된 자연수의 합이 N이 되는 경우의 수(count)를 구한다.

풀이 과정

📌 투 포인터 이동 방법
start를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 작은 값을 빼는 것과 같고, end를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하여 더 큰 값을 만들기 위함이다.연속된 자연수의 합이 N과 같을 때는 경우의 수를 증가시키고, end를 오른쪽으로 이동시킨다.

sum < N 일 경우 : 종료 인덱스 증가(end++), sum 값 변경(sum += end)
sum = N 일 경우 : count 증가, 종료 인덱스 증가(end ++), sum 값 변경(sum += end)
sum > N 일 경우 : sum 값 변경(sum -= start), 시작 인덱스 증가(start++)

• start = 1, end = 1, sum = 1
  $sum<N$ 이므로 end를 증가시키고, sum을 증가한 end값을 더한 값 3로 변경한다.
  
• start = 1, end = 2, sum = 3
  $sum<N$ 이므로 end를 증가시키고, sum을 증가한 end값을 더한 값 6로 변경한다.
  sum과 N이 동일한 값이 될 때 까지 end를 증가시키면서 반복한다.
  
• start = 1, end = 5, sum = 15
  $sum=N$ 이므로 count와 end를 증가시키고, sum을 증가한 end값을 더한 값 21로 변경한다.
  
• start = 1, end = 6, sum = 21
  $sum>N$ 이므로 sum을 start값을 뺀 값 20으로 변경하고, start값을 증가시킨다.
  
• start = 2, end = 6, sum = 2
  $sum>N$ 이므로 start값을 뺀 값 18으로 변경하고, start값을 증가시킨다.
  

위의 과정을 end 인덱스가 N이 될 때가지 반복하여, 결과 값 count를 출력한다.

소스 코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int start = 1;  // 시작 포인터
        int end = 1;    // 종료 포인터
        int sum = 1;    // 연속된 자연수의 합
        int count = 1;  // 연속된 자연수의 합이 N과 같은 경우의 수

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

        System.out.println(count);
    }
}

핵심 정리

투 포인터 알고리즘을 기억하자 !

백준 2018 문제를 통해 투 포인터의 기본적인 동작 과정을 학습하였다. 투 포인터는 2개의 포인터를 이동시키면서 연산을 진행하여 시간 복잡도를 최적화한다. 이때, 문제마다 두 개의 포인터의 시작 위치와 연산 과정은 다를 수 있으므로 다양한 문제를 풀어보면서 투 포인터 알고리즘을 활용하는 능력을 키워보면 좋을 것 같다.😎