표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
✅ 문제 풀이
n을 입력 받고 나서 크기가 n+1*n+1인 2차원 벡터를 생성해준다.
그리고 배열의 첫번째 행은 사용하지 않을 것이고, 첫번째 열은 모두 0으로 초기화 해준다.
이 배열은 각 행마다의 누적 합을 갖도록 한다.
배열 값을 입력 받을 때, 해당 행과 열에 해당하는 값은, 배열값+이전열 값을 더하여 누적하도록 한다.
이렇게 누적합을 가진 배열을 가지고, m번의 좌표 입력을 받을 것이다.
좌표의 x1부터 x2까지, y2까지의 누적합에서 y1-1까지의 누적합을 뺀 결과를 누적하여 각각의 answer를 구하고 출력한다.
만약 x1=2, y1=2, x2=3, y2=4이면 누적합 배열의 2행부터 3행까지, 각 항의 4열까지의 누적합-1열까지의 누적합을 하면 2,3,4열을 합한 값이 되는 것이므로 반복적인 덧셈을 피할 수 있다.
이렇게 누적합은 반복적인 연산을 줄여주어서 시간복잡도를 낮추어주는 장점이 있다.
✏ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> sum(n+1, vector<int>(n+1));
for (int i = 1; i < n+1; i++) {
sum[i][0] = 0;
for (int j = 1; j < n+1; j++) {
cin >> sum[i][j];
sum[i][j] += sum[i][j - 1];
}
}
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int answer = 0;
for (int j = x1; j <= x2; j++) {
answer += (sum[j][y2] - sum[j][y1 - 1]);
}
cout << answer<<"\n";
}
return 0;
}
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
[입력] 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
[출력] 첫째 줄에 경우의 수를 출력한다.
수열에서 연속적인 값들의 합이 M과 같은 경우의 수를 구하는 문제이다.
✅ 문제 풀이
일단 누적합을 나타내는 sum에는 수열에서 첫번째 값을 넣어두고 시작한다.
실행시간 조건이 0.5초이기 때문에, for문에 의한 순회는 한번을 최대로 해야 한다.
그럼 부분 합을 어떻게 구할 수 있을까?
두 포인터를 이용해서, 시작 지점과 끝 지점을 가리키도록 한다.
그것을 각각 s와 e로 하고, 수열의 인덱스를 가리키도록 한다.
처음에는 s와 e를 0으로 시작한다. 따라서 sum도 수열의 첫번째 값만을 담고 있어야 한다.
그렇게 해서 s<=e를 만족하는 한 계속 경우의 수를 찾아갈 것이다.
if문을 통해 현재의 sum값과 M을 비교한다.
만약 sum이 M보다 작으면, 더 더해주어야 하기때문에 e를 하나 늘리고, 현재 e가 가리키는 값을 sum에 더해준다. 이때 주의할 점은, 하나 늘어난 e가 N을 넘지 않아야 한다는 것이다. N을 넘지 않았을 경우에만 e가 가리키는 값을 sum에 더해주면 된다.=>유효성을 확인하는 부분이다.
만약 sum이 M과 같다면, 하나의 경우가 되는 것이므로, 경우의 수를 카운트하는 answer를 하나 늘려준다. 그리고 수열의 모든 값은 자연수이기 때문에, s를 늘리면 값을 줄고, e를 늘리면 값이 늘어나게 되는 건 분명하다. 따라서 이 경우에는 s와 e를 둘다 하나씩 늘리도록 한다.
만약 sum이 M보다 크다면, 빼주어야 하기때문에, sum에서 현재 s가 가리키는 값을 빼준다. 그리고 여기서 주의할 점이 있다. 만약 s가 e와 동일했었다면 다음 값을 sum에 넣어주어야 하기 때문에, s와 e를 둘다늘리고, 이 둘이 가리키는 값을 sum에 넣어주도록 한다. s와 e가 동일하지 않았다면 s를 하나 늘려주면 된다.
그리고 for문을 다 순회한 후에는 answer를 출력해주면 된다.
☑ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
int arr[10000];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int sum = arr[0];
int answer = 0;
for (int s = 0, e = 0; s <= e;) {
if (sum < M) {
e++;
if (e < N) sum += arr[e];
else break;
}
if (sum == M) {
answer++;
sum -= arr[s];
s++;
e++;
if (e < N) sum += arr[e];
else break;
}
if (sum > M) {
sum -= arr[s];
if (s == e && e < N - 1) {
s++;
e++;
sum += arr[e];
}
else {
s++;
}
}
}
cout << answer;
}
누적합 배열을 v라고 할 때, 만약 K=2이면 v[2]-v[0]은 두번째 값까지 더한 값에서 0번째 값까지 더한 값을 빼준 것이고, 이 값은 첫번째값과 두번째값을 더한 것이므로, 단순히 빼기를 통해 구간의 합을 구할 수 있고, 이로써 중복적인 더하기 연산을 피할 수 있으므로 시간을 단축할 수 있다.
예시
예시
주어진 예시에서 5개만을 가져와 보았다.
주어진 5개의 숫자값들이 위의 배열과 같을 때, 아래 v배열은 각 값들의 누적합을 차례로 1번 인덱스부터 채워넣는다.
하나씩 살펴보면, v[1]에는 첫번째 값인 3을, v[2]에는 두번째값까지 더한 값(3+(-2))인 1을, v[3]에는 세번째값까지 더한...
이제 K가 2이므로, 연속한 두 값씩 더한 값을 구해보자. 이는 이미 구해둔 v[K]-v[0] 연산만을 통해 구할 수 있다.
첫번째 연속합을 max로 지정해주고, for문을 통해 K+1부터 N까지 진행하면 된다.
이 방법은, cin으로 숫자값들을 받을 때, 동시에 배열에도 누적합을 더해 놨기 때문에, 이 값을 이용해 차 연산만 해주고, 그 연산 결과가 가장 큰 값을 반환하면 되므로, 시간효율이 아주 좋다!
아래는 전체 코드이다.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N,K;
cin>>N>>K;
vector<int> v(N+1,0);
for(int i=1; i<N+1; i++){
int temp;
cin>>temp;
v[i]=v[i-1]+temp;
}
int max=v[K];
for(int i=K+1; i<N+1; i++){
max=(max<v[i]-v[i-K])?v[i]-v[i-K]:max;
}
cout<<max;
return 0;
}
이전에 유사한 누적합 문제를 풀어봐서 문제를 보자마자 바로 "누적합!!!"하며 풀 수 있었다.
코딩테스트를 준비하면서 여러 문제를 풀다보니, 점점 문제의 유형이 눈에 보이기 시작한 것 같다.
