[투포인터] 백준 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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

시간제한 : 2초

 

 

자연수 N의 최대 크기가 천만이기 때문에, O(nlogn)의 복잡도를 가지는 알고리즘도 N이 천만일 때 약  2억3천 번의 연산이 필요하기 때문에 위험해 보인다.

 

따라서 O(n)의 시간복잡도를 가지는 방식으로 해결해야 한다.

 

그렇기 때문에 투 포인터 알고리즘을 사용하여 해결했다.

 

투포인터 알고리즘은 특정한 합을 가지는 연속된 수열들을 O(n)의 복잡도로 탐색 할 수 있다. 

 

 

 

투포인터 알고리즘

start와 end 와 같은 이름으로 포인트 이름을 설정

 

초기에는 start = end = 0으로 시작하며

 

대소 관계는

start <= end 에 해당한다

 

 2개의 포인터는 계산할 부분 배열의 시작과 끝을 가르킨다.

 

이 방식을 통해 특정한 합을 가지는 연속 수열을 찾을 수 있다.

 

1. start와 end를 0으로 둔다.

 

2. sum의 초기값은 end와 start가 같은 자리에 있으므로 그 자리에 해당하는 값이다.

 

3. 구하고자 하는 합의 특정 값을 target으로 지정하고

 

4. sum < target 이라면 end를 1 증가시키고. sum에 end의 값을 더한다.

5. sum > target 이라면 sum에서 start자리의 값을 빼고. end를 1 증가시킨다.

6. sum == target 이라면 count 또는 수열을 저장한다. 수열이라면 (end와 start만으로 수열을 구할 수 있으니) 그러나 수열 저장 과정은 O(n) 이므로 O(n^2) 의 시간 복잡도를 갖게 될 수 있다. 

 

7. 해당하는 방식으로 start = end가 될때까지 진행한다. 또는 count를 1로 두고 (N 그자체의 합은 항상 경우의수가 동일하므로) end 가 N이 될때까지 진행한다.

 

 

N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 target이 되는 경우의 수는 구간합을 구간 배열로 O(1)으로 구한다 해도 부분배열이 가능한 모든 원소 조합을 고려하는 방식이기 때문에 N * (N + 1) / 2  이므로 시간복잡도는 O(n^2) 이다.

 

그러나 투포인터 알고리즘을 활용하면  O(n) 을 가질 수있다.

 

해답

class Solution {
  public void solve() throws IOException {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int count = 1;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;

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


  }
}

 

이 풀이에서는  연속된 수열이 아닌 그저 자연수 15의 연속된 수의 합 개수를 구하는 것이기 때문에 배열을 사용할 필요 없이 

 

start와 end의 계산 만으로 합의 수를 구할 수 있었다.

 

또한 주어진 수 N 그 자체가 target이므로 count에 1을 초기화 해둔 상태로 end가 N이 될때까지만 반복하도록 하여 

반복 횟수를 줄였다.

 

입력값은  N 하나이므로 BufferedReader 말고 scanner를 사용했다.