2018번 난이도:실버 5(연속된 자연수의 합 구하기)-투 포인터

 

이 문제의 시간 제한은 2초, N의 최댓값은 100000000이므로 제한 시간을 맞추기 위해서 투 포인트를 사용해야 합니다.

 

시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현해보자

 

풀이 방식을 두 가지 정도 생각해보았습니다.

 

첫번째 풀이 방식

 

1. 시작인덱스부터 종료 인덱스까지 탐색하면서 합이 N이 될 때를 카운트한다.

 

2. 만약 sum하고 N 값이 같을 때는 종료 인덱스를 더 큰 쪽으로 한 칸 옆으로 보내고, sum값을 바뀐 종료 인덱스를 더 한 값으로 초기화한다. 그리고 count도 시켜준다.

 

3. 만약 sum보다 N이 작을 때는 종료 인덱스를 더 큰 쪽으로 한 칸 옆으로 보내고, sum값을 바뀐 종료 인덱스를 더 한 값으로 초기화한다.

 

4. 만약 sum이 N보다 작다면 sum에서 시작인덱스 값을 빼주고,  시작인덱스를 더 큰 쪽으로 한 칸 옆으로 보낸다. 

 

#include <iostream>
#include<string>

using namespace std;

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

	int num;
	cin >> num;
	int sum = 0;
    int start index=1;
    int end_index=1;
    int sum=1
	int count = 0;

	while(end_index !=N){
    	if(sum==N){
        count++;
        end_index++;
        sum+=end_index;
        }
        else if(sum>N){
        	sum+=start_index;
            start_index++;
        }
        else{
        	end_index++;
            sum+=end_index;
            }
        }      
	cout << count+1;
}

 

 

두 번째 방식

 

1. for문을 활용해서 1부터 N 전까지 반복시킨다.

 

2. 만약 N의 값이 sum보다 작아지면 sum을 0으로 초기화 시킨다.

 

3. 만약 N의 값이 sum 값하고 같다면 count를 하고 sum을 0으로 초기화시킨다.

 

4. 만약 N값이 sum보다 크다면 그 반복문의 해당하는 숫자를 더해준다. 

 

#include <iostream>
#include<string>

using namespace std;

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

	int num;
	cin >> num;
	int sum = 0;
	int count = 0;

	for (int i = 1;i < num;i++) {
		for(int j=i;j<num;j++)
			if (num < sum) {
				sum = 0;
				break;
			}
			else if (num == sum) {
				count++;
				sum = 0;
				break;
			}
			else {
				sum += j;
			}
	}
	cout << count+1;

}