Do it! 알고리즘 코딩테스트 | 1. 자료구조 - 투 포인터 | 006 연속된 자연수의 합 구하기

문제 정보 백준 2018번 수들의 합 5 https://www.acmicpc.net/problem/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 

15

예제 출력 1 

4

 

//내 코드
#include<iostream>
using namespace std;
int main(){
    int n, cnt=0, sum=0;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            sum += j;
            if(sum == n){
                cnt++;
                sum = 0;
                j = n+1;
            }
            else if(sum > n){
                sum = 0;
                j = n+1;
            }
        }
        
    }
    cout << cnt;
}

 

//정답 코드
#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
    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) {   // 현재 합이 답보다 큰 경우
            sum = sum - start_index;
            start_index++;
        }
        else {                // 현재 합이 답보다 작은 경우
            end_index++;
            sum = sum + end_index;
        }
    }
	cout << count << "\n";
}

 

내 코드도 백준에서 맞긴 했지만 데이터가 커지면 틀릴 듯 하다. 그 이유는 내 코드는 배열을 완전탐색 하기 때문이다.

정답 코드에서는 포인터를 밀어내는 방식으로 탐색 한다.

 

1 + 2 + 3 + 4 = 10이기에 15보다 작으므로 end를 증가하고 sum에 end(5)를 더한다.

그렇게 된다면 sum이 15가 되기에 답을 찾아서 count를 증가하고 end를 증가하고 sum에 end(6)을 더한다.

그러면 21이기에 15보다 크므로 sum에 start(1)를 빼고 start를 증가시킨다.