백준 2018번 수들의 합5 (C++)

2018번: 수들의 합 5

문제 분석

N이라는 숫자를 '연속'된 자연수의 합으로 표현하고, 이 조합의 개수를 구하는 문제이다.

주목해야 할 점은 3가지라고 생각한다.

1, 연속된 자연수.

2. 메모리의 크기.(32MB)

3. N의 크기

 

1. 연속된 자연수

- 자연수가 1개 혹은 여러 개가 되어도 연속된 자연수라면 조합에 포함이 된다.

즉, N이라는 숫자의 연속된 자연수는 최소 1개 이상이 될 것이다. 이 외의 연속된 자연수를 찾기 위해서는, 구간 합의 개념을 이용하면 된다. 구간 합의 개념을 모른다면 아래 링크로 공부하고 와주길 바란다.

구간 합

---

2. 메모리 크기 + 3. N의 크기

 두 개의 문제가 서로 연관되어 있어 함께 해결하고자 한다. N의 크기는 10,000,000이 최대이다. 시간복잡도가 O(N)이어야한하고, 메모리가 32MB인 것을 보아, 구간 합에서의 합 배열을 사용하면 안된다는 것을 알 수 있다.

 

만약 합배열을 사용한다면?

- int 변수 하나당 4bytes를 차지한다. 합배열의 크기는 N일 것이며, 총 40,000,000bytes를 차지한다.

(40,000,000 = 40MB) 이 외에 사용하는변수들을 합친다면, 32MB를 넘는 메모리를 차지하게 될 것이다.

---

문제 풀이

1

2

3

4

5

6

7

8

9

10

      start             ->                                                       end             ->

 

구간 합을 배열을 사용하지 않고, 개념만 이용하면 된다.

시작점, 끝점 두 가지를 두고, 이를 이동시키면서 조합을 파악하면 된다. (투 포인터)

구간 합으로 기초 개념을 다지고, 투 포인터를 공부하면 훨씬 쉽게 이해할 수 있을 것이다.

[Algorithm] 투 포인터(two pointer) 완.전.정.복

 

sum을 시작점과 끝점사이에 있는 변수들의 합이라고 한다. N=15라고 할 때,

1. 시작점이 4, 끝점이 7이라고 한다면, sum 22는 N보다 크기에, start를 앞으로 이동시킨다.

2. 시작점이 2, 끝점이 4라고 한다면, sum 9는 N보다 작기에, 끝점을 한칸 앞으로 이동시킨다.

3. 시작점이 1, 끝점이 5라고 한다면, sum 15는 우리가 찾고자 하는 N이기에 조합에 추가된다. 후에 끝점을 이동시킨다.

 

3가지 조건을 만족할 때까지, 반복한다면? 위의 문제분석 3가지 모두를 만족하는 코드가 생성된다!

 

코드와 주석으로 이해를 돕겠다.

 

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

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

	int N, num = 1, start = 1, end = 1, sum = 1;
    // start : 시작, end : 끝, sum : 시작과 끝의 총합, num : 조합의 개수
	cin >> N;
    
	while (end < N) {
		if (sum > N) { // 1에 해당하는 조건
			sum -= start; 
			start++;
		}// sum에서 기존의 start를 빼준 뒤, start를 증가시킨다.
        
		else if (sum < N) { // 2에 해당하는 조건
			end++;
			sum += end;
		}// end를 먼저 증가시키고, sum에 증가된 end값을 더해준다.
        
		else { // 3에 해당하는 조건
			num++;
			end++;
			sum += end;
		} // 조합을 찾으면 이 뒤의 조합까지 찾아야 하기에, 증가된 end값을 더해준다.
	}

	cout << num;
	return 0;
}

코드 리뷰는 언제나 환영입니다!!