[C++] 백준 2003번 수들의 합 2

1. 문제이해

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있을 때, 이 수열의 i번째 수부터 j번째 수까지의 합

A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

주어진 수열에서 합이 M이 되는 연속되는 경우의 수를 구하는 문제이다.

연속된 수들의 합만 취급하기에 그다지 어려운 문제는 아닌것 같지만,

조건이 몇가지 있기에 잘 따져서 코드를 짜면 될 것 같다.

 

필자는 아래와 같은 형식으로 풀이 했다.

 

start_index, sum_index, sum, count라는 변수를 이용했다.

여기서 중요한 것은 start_index와 sum_index이다.

두 변수는 각각 더하기를 시작할 요소의 인덱스, 현재 더할 요소의 인덱스이다.

 

지금까지 더한 요소들의 합(sum)이 입력받은 M보다 클 경우, 같은 경우, 작을 경우로 나누어

각각 위와 같이 처리해주는 식으로 풀이했다.

자세한 구현 과정은 아래 소스코드를 참조하자.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	long long N, M;
	long long input;
	vector <long long> v;

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> input;
		v.push_back(input);
	}


	int start_index = 0;
	int sum_index = 0;
	long long sum = 0;
	int count = 0;

	while (true) {
		// 시작 인덱스가 M의 사이즈보다 크면 탐색 종료
		if (start_index >= v.size()) {
			break;
		}

		sum += v[sum_index];

		if (sum > M) {
			start_index++;
			sum_index = start_index;
			sum = 0;
		}

		else if (sum == M) {
			start_index++;
			sum_index = start_index;
			sum = 0;
			count++;
		}

		else {
			sum_index++;
			// 더하는 인덱스가 M보다 클 경우, 시작 인덱스를 키우고 재탐색
			if (sum_index >= v.size()) {
				start_index++;
				sum_index = start_index;
				sum = 0;
			}
		}

	}

	cout << count;


	return 0;
}

주의해야 할 점은 N과 M의 범위가 꽤나 크다는 점이다.

백준을 풀다보면 알겠지만 이렇듯 범위가 꽤나 큰 문제들이 많이 나온다..

N은 상관없으나, M의 경우는 혹시 몰라 long long으로 처리해주었다.

 

N, M과 벡터에 들어갈 요소들을 입력받은 뒤, 다음과 같은 4가지 변수를 설정했다.

int start_index = 0;  // 더하기를 시작할 요소의 인덱스
int sum_index = 0;  // 현재 더할 요소의 인덱스
long long sum = 0;  // 지금까지 더한 요소들의 합
int count = 0;  // 최종적으로 구하고자 하는 합이 M이 되는 경우의 수

 

그리고 위에서 정의한 3가지 경우에 맞추어 if-else 문을 작성했다.

( 합(sum)이 입력받은 M보다 클 경우, 같은 경우, 작을 경우)

위 그림에서 작성한 부분과 동일하기 때문에 설명은 생략하도록 하겠습니다.

 

한가지 더 주의해야할 점은 start_index와 sum_index가 요소의 개수(N / v.size())를 넘어가는 경우이다.

이를 처리하기 위해 while문 상단에는 start_index가 v.size()보다 클 경우 종료하도록 했으며,

마지막 else문에서 sum_index가 v.size()보다 클 경우 start_index를 키워 재탐색 하도록 했다.

 

 

---

정말 오랜만의 포스팅입니다..😢

사실 어제 자바 프로그래밍 연습문제 풀이를 업로드하긴했지만,

코딩테스트 문제를 풀고 업로드하는건 엄청 오랜만인 것 같아요

요즘 정말.. 눈코뜰 새 없이 바쁘다 보니..^^ 어느새 1년 중 2달 정도만을 남겨두고있네요

 

이 글을 보시는 여러분, 모두 열심히 하시는 모습이 정말 멋있으십니당!👍👍

다들 즐거운 연말 보내시고 다른 좋은 포스팅으로 돌아오겠습니다!