2018번 - 연속된 자연수의 합 구하기(C++)

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을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

라는 간단한? 문제이다.

 

처음엔 그냥 1부터 갯수를 늘려가며 경우의 수를 다 구해볼까 했는데 10,000,000이 최댓값인걸 보니 당연히 안되겠다 싶었다.

 

그래서 책을 봤는데 투포인터라는 방법을 사용했다.

 

말 그대로 포인터가 두개인 것인데.

이런식으로 시작점과 끝점을 나타내는 포인터 두개를 둔다.

 

우리는 이 투포인터로 연속된 숫자들로 N을 표현하는 가짓수를 카운트 할건데,

 

이 투포인터로 대체 뭘 어떡해야할까?

 

start 포인터를 시작점. end 포인터를 끝점이라고 부르겠다.

 

count가 되는 조건 = 시작점 ~ 끝점의 합이 N인 경우

count가 안되는 조건 = 시작점 ~ 끝점의 합이 N이 아닌(크거나 작은) 경우

계산이 끝나는 조건  = 끝점이 N일 경우

 

이제 그림을 보자

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

일단 우리는 시작점과 끝점 모두 1에 둘거다.

당연히 1은 15가 아니다(작다).

그래서 우린 끝점을 하나 뒤로 보낸다. 1~2라 해도 당연히 안된다.합은 3으로 여전히 작다.

 

그렇게 15가 될때까지 끝점을 뒤로 보내보겠다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1+2+3+4+5 = 15 = N이다. 이때 count++을 한다.

 

이제 다시 끝점을 하나 늘린다.

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

합이 21이 되었고 N보다 크다.

그렇다면 끝점을 뒤로 보내면 합이 더 커질뿐이고 다시 앞으로 보낼수도 없다.

그렇다면 시작점을 하나 뒤로 보냄으로써 합을 줄이는 효과를 가져올 수 있다.

그렇게 합이 N보다 클때마다 시작점을 뒤로 보냈더니

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

다음과 같이  4+5+6으로 15가 되었다.

 

우리는 이 과정을 보면 시작점~끝점까지의 합이 N보다 작거나 같다면 끝점을 뒤로 보내어 합의 크기를 늘리고 

 

N보다 크다면 시작점을 뒤로 보내어 합의 크기를 줄여 N이 되는 연속된 숫자의 합을 찾아왔다!

 

이걸 코드로 바꿔보자

#include <iostream>

using namespace std;

int main(void) {

	//cin,cout의 속도를 빠르게 해주는 코드 자세한 설명은 이전 문제들에 있다.
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n; //숫자 N 
	int count = 1;//자기 자신을 카운트하고 시작
	int start_point = 1; //시작점
	int end_point = 1; //끝점
	int sum = 1; //합계 우린 첫 숫자(1)을 합치고 시작한다.

	//끝점이 n이면 종료
	while (end_point != n) {
		if (sum == n) { //합이 N과 같다면
			count++; //카운트
			end_point++; //끝점 뒤로 보내기
			sum = sum + end_point; //합계에 끝점 더하기(포인트라곤 했지만 인덱스라던가 그런 의미는 아니다.)
		}

		else if (sum > n) { //합이 N보다 크다면
			sum = sum - start_point; //합에서 이전 시작점값을 빼주고
			start_point++; //시작점 뒤로 보내기
		}

		else { //합이 N보다 작다면
			end_point++; //끝점 뒤로 보내기
			sum = sum + end_point; // 합계에 끝점 더하기
		}
	}
	cout << count << "\n";

	return 0;
}

이렇게 되었다!

 

생각보다 간단한 문제였다.