[BOJ] 백준 #2018. 수들의 합 5 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/2018

• 알고리즘 분류: 수학, 투 포인터
• 난이도: Silver Ⅴ

💬 풀이 (1)

자연수 N을 ‘연속된 자연수의 합’으로 만드는 경우의 수를 구하는 문제. 수학적으로 간단하게 풀리는 문제일 거라고 생각은 했지만, 방법이 생각 안나서 좀 헤맸다.

1부터 N쪽으로 그냥 계속 더해가다가 그 합이 N이 되면 cnt++하는 방식으로 풀 수 있다. 이런 풀이 방식은 쉽고 직관적이지만, 보통 시간 초과다.

👩‍💻 코드(1) - 이중 for문

C++

#include <iostream>

using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;

	int cnt = 0;
	int total;
	for (int i = 1; i <= N; i++) {
		total = 0;
		for (int j = i; j <= N; j++) {
			total += j;
			if (total == N) {
				cnt++;
				break;
			}
			else if (total > N) {
				break;
			}
		}
	}

	cout << cnt;

	return 0;
}

💬 풀이 (2) - 투 포인터

✔ 투 포인터

이 문제는 "투 포인터 알고리즘"으로 쉽게 풀린다고 한다.
별로 안 어렵다. 원래 배열에서 이중 for문으로 이중 탐색을 하면 O(N^2)이 걸리는데, 이 방법 대신 포인터 두 개를 두고 걔네를 잘 움직여서 O(N)에 해결하는게 바로 투 포인터 알고리즘이다. 실제로 이분탐색 문제가 투포인터로도 풀리거나, 투포인터 문제가 이분탐색으로도 풀리는 경우가 되게 자주 있다.

여기서 '포인터'라고 하는 것은 C에서의 포인터라기보다 그냥 커서라고 생각하면 된다.

[YouTube] (BaaarkingDog, [바킹독의 실전 알고리즘] 0x14강 - 투 포인터)

알고보니 예전에 들은 강의에서 배운 내용이었다..ㅎ

1. 투 포인터 이용. 많은 참고) https://velog.io/@jms8732/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0
2. (주의) 자기 자신도 답에 포함되므로 cnt가 아닌 cnt+1을 출력한다.

👩‍💻 코드(2)

C++

#include <iostream>

using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;

	int left = 1, right = 1;
	int total = 0;
	int cnt = 0;
	while ((left <= right) && (right <= N)) {
		if (total < N) {
			total += right++;
		}
		else if (total == N) {
			cnt++;
			total -= left++;
		}
		else {
			total -= left++;
		}
	}

	cout << cnt + 1;

	return 0;
}