[백준 2018번] 연속된 자연수의 합 구하기 - 투 포인터

문제

어떠한 자연수 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. 나의 풀이

1. 연속된 자연수들의 합이기 때문에 합 배열을 이용해보려고 생각했다.
2. 먼저 주어진 정수 N 그 자체가 카운트 되므로 count 변수는 1로 초기화하였다.
3. 합 배열끼리 빼면 연속된 자연수가 나타난다.
   ex) 합배열[5] - 합배열[2] = (1 + 2 + 3 + 4 + 5) - (1 + 2) = 3 + 4 + 5
4. 이를 이용해서 이중 반복문을 통해 합 배열간에 차이가 N과 같으면 count 를 증가시키고 내부 반복문을 break한다.

cf) 처음에는 외부 반복문을 1부터 N까지 돌렸으나 나중에 생각해보니 굳이 N까지 돌릴 필요가 없었다.

N이 20이라고 가정해보자. N 을 2로 나눈 수인 10을 넘은 숫자들은 더하면 무조건 N보다 크기 때문에 계산할 필요가 없다.

홀수인 경우에도 생각해야하므로 Math.round를 이용해 반올림하여 절반까지만 반복문을 돌리도록 하였다.

 

Scanner scan = new Scanner(System.in);

int num = Integer.parseInt(scan.nextLine());
int count = 1; //경우의 수인데 num 혼자 있을 경우를 미리 카운트한다.

int[] arr = new int[num + 1];       //합배열 생성

for (int i = 1; i <= num; i++) {    //합배열 초기화
arr[i] = arr[i - 1] + i;
}

// num의 절반을 넘어선 자연수의 합은 무조건 num 보다 크기 때문에 num/2 까지만 계산
for (int i = 1; i <= Math.round((float)num/2); i++) {
    for (int j = 0; j < i; j++) {
        //합배열의 차이가 num과 같으면 count증가, 반복 중지
        if(arr[i] - arr[j] == num) {
            count++;
            break;
        };
    }
}

 

하지만............. 위 코드로 정답을 제출하였지만 시간 초과가 나왔다..............

노트북으로 최대값인 10,000,000 을 N으로 대입해봤는데 연산이 끝이 안난다...........ㅠㅠㅠㅠㅠㅠㅠㅠ

시간제한이 2초인데 2분이 넘게 걸리네 ㅎㅎ...

 

2. 교재 풀이

교재에서는 투 포인터라는 알고리즘을 사용하였다.

 

문제 분석

알고리즘을 선택할 때 N의 범위를 먼저 보자

N의 범위가 10,000,000으로 매우 크기 때문에 O(n logn)의 시간복잡도 알고리즘을 사용하면 제한 시간을 초과하게 된다. O(n)의 시간복잡도를 가진 투 포인터 알고리즘을 사용하도록 한다.

투 포인터 이동 원칙

• sum > N (sum이 N보다 클 경우)
  - sum에서 start_index를 뺀 후 start_index 의 값을 1 증가시킨다.
  - sum - start_index;   
    start_index++;
• sum < N (sum이 N보다 작을 경우)
  - end_index를 1 증가시킨 후 sum에 증가된 end_index를 더한다.
  - end_index++;
    sum = sum + end_index;
• sum == N (sum이 N과 같을 경우)
  - count 1 증가시키고 end_index를 1 증가시키고 sum에 더한다.
  - count++;
    end_index++;
    sum = sum + end_index; 

N == 15 라고 가정하였을 때

1. 1~15를 담은 int 배열을 생성한다.
2. 두 개의 포인터 (start_index, end_index)를 1로 설정한다.
3. sum, count 변수 초기화
   sum = 1 (start_index ~ end_index까지의 합)
   count = 1 ( 15는 자체가 하나의 연속된 숫자이므로) 
4. 투 포인터 이동 적용

 

Scanner scan = new Scanner(System.in);

int num = Integer.parseInt(scan.nextLine());
int count = 1;  //경우의 수인데 num 혼자 있을 경우를 미리 카운트한다.
int si = 1; 	// start_index
int ei = 1; 	// end_index
int sum = 1;	// si + ei 이지만 초기화는 1로 진행

while (si != num) {
    if(sum < num) {
        sum += ei;
        ei++;
    } else if (sum > num) {
        sum -= si;
        si++;
    }else{
        count++;
        ei++;
        sum += ei;
    }
}

System.out.println("count = " + count);

 

투 포인터 알고리즘을 적용해서 코드를 실행시켜봤더니 1초도 안걸려서 답이 나온다.

내가 짠 코드는 이중 반복문을 사용했으니 O(n²) 의 시간복잡도를 가지는 것으로 예상은 했지만 알고리즘 시간 복잡도에 따른 시간이 얼마나 소요되는지 감이 잡히지 않았는데 시간 복잡도에 대해서 좀 더 공부를 해봐야할 것 같다.