백준2018 - 수들의 합 5

문제

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

예제 입력 1
15
예제 출력 1
4

---

풀이

public class Q2018_수들의합5 {
    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;
        while (end != n){
            if (sum == n){
                count++;
                end++;
                sum = sum + end;
            }else if(sum < n){
                end++;
                sum = sum + end;
            }else{
                sum = sum - start;
                start++;
            }
        }
        System.out.println(count);
    }
}

리뷰

• 투포인터를 사용하는 문제로 투 포인터는 2개의 포인터를 이용해 알고리즘의 시간 복잡도를 최적화하는 방법이다. 문제를 리뷰하며 정리해보자.

• sum은 누적합
  n은 주어진 숫자 N
  count는 숫자 N이 되는 구간합
  start는 구간 합의 시작 포인터
  end는 구간 합의 끝 포인터

• 일단 처음에 주어지는 숫자를 count에 누적하고, sum은 1로 초기화해주었다.
  예를 들어 15인 경우 15가 나올 수 있는 경우의 수를 누적한 것이다.

1. while문을 이용해 end포인트가 주어진 숫자 N이 아닐때까지 루프를 돌도록 설정하였다.
   • 처음에 N을 count에 누적해주었기 때문에 start포인트를 기준으로 사용하지 않고, end포인트를 기준으로 사용하였다.
2. 루프를 돌며 조건문에 따라 각 수를 sum에 누적해주는데,
   1. sum == n일 때,
      주어진 숫자와 sum이 일치하므로 count를 1 증가시키고, end포인트를 1증가시킨 뒤 해당 숫자를 sum에 누적한다.
   2. sum < n 일 때,
      주어진 숫자보다 sum이 작으므로 end포인트를 1증가시키고, 해당 숫자를 sum에 누적해준다.
   3. sum > n 일 때(그 외),
      주어진 숫자보다 sum이 크므로, 구간합 sum에서 start포인터의 해당 숫자를 빼주고, start포인터를 1증가시킨다.
3. 이 과정을 반복하며 end포인트가 n과 일치하면 루프를 끝내고 결과를 출력한다.

• 연속된 자연수의 합을 구하는 문제이므로 두개의 포인터를 이용하여 시작과 끝 포인터를 각각 경우에 따라 이동시켜줌으로 연속된 수의 합이 n과 같은 모든 경우의 수를 구할 수 있다.