[백준 BOJ] 11659번 구간 합 구하기 4 (C++/cpp)

문제 설명

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

11659번: 구간 합 구하기 4

 

접근 방법 - 최적의 합계 연산 문제

백준의 11659번 문제는 합계 연산에 있어 최적의 방법을 탐색해야 하는 문제이다.

해당 문제는, 주어진 숫자들에 대하여 입력받은 범위에서의 합계를 구하여 출력해야 하는 문제이다.

이 문제는 단순 반복문을 통하여 총합계를 구하면 될 문제로 보일 수 있지만, 단순히 그렇게 풀면 시간 초과가 걸릴 것이다.

그렇기 때문에, 각 경우에 따라 최적의 방법을 찾아 합계를 연산하도록 해야 한다.

필자의 경우엔 총합계를 구하는 데에 탐색할 원소의 개수가 많은지 적은지에 따라 연산 방법을 달리하였다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 특히나 시간 초과가 계속 걸려 고민이라면, 아래의 설명과 코드를 참고하길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 특정 수열에 대한 값을 저장할 배열(arr)을 전역 변수로 선언해둔다.

 

2) 수열의 길이(n)와 합계를 구할 범위의 개수(t)를 입력받는다.

 

3) n의 크기만큼 arr의 값을 입력받는다.

이와 동시에, 미리 0으로 초기화해둔 sum 변수에 순차적으로 더한다.

(이렇게 하면, sum의 값은 arr에 대한 총합계가 된다.)

 

4) t의 크기만큼 반복문을 수행하여 아래의 연산을 취한다.

- 합계를 구할 범위(a, b)를 입력받는다.

- 해당 범위에 대한 합계를 저장할 변수 s를 0으로 초기화하여 선언해둔다.

- 만일 합계를 구할 범위가 arr의 총개수의 절반보다 적다면, 일일이 하나씩 더하는 것이 더 효율적이다.

따라서, 이 경우엔 a부터 b까지 반복문을 돌려 s에 각 배열값들을 더하도록 한다.

- 다만 합계를 구할 범위가 arr의 총개수의 절반보다 크다면, 총합계에서 범위 밖의 값들을 하나씩 빼는 것이 더 효율적이다.

따라서, 이 경우엔 미리 구해둔 sum 값에 범위 밖의 값들의 합계를 빼서, 해당 값을 s에 저장하도록 한다.

 

5) 최종적으로 저장된 s의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11659번 코드
int arr[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, t;
	cin >> n >> t;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;

		int s = 0;
		if (b - a < n / 2) {
			for (int j = a; j <= b; j++) {
				s += arr[j];
			}
		}
		else {
			for (int j = 1; j < a; j++) {
				s += arr[j];
			}
			for (int j = b + 1; j <= n; j++) {
				s += arr[j];
			}
			s = sum - s;
		}
		cout << s << endl;
	}
}

 

제출 결과

(2022.05.09 백준 11659번 문제 제출 결과)