728x90
구간 합 구하기 4 출처 : 11659번: 구간 합 구하기 4 (acmicpc.net)
나의 풀이 :
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
vector<long> dp(N + 1);
dp[0] = 0;
for (int i = 1; i <= N; i++) {
long num;
cin >> num;
dp[i] = dp[i - 1] + num;
}
for (int i = 0; i < M; i++) {
int start, end;
cin >> start >> end;
cout << dp[end] - dp[start - 1] << '\n';
}
return 0;
}
입력받음과 동시에 dp 배열의 dp[N]
에 1부터 N까지의 누적합을 저장한다.
그리고 M번의 start(시작점)과 end(종료점)을 입력받으면 dp[end] - dp[start-1]
을 출력한다.
참고로 아래 코드를 삽입하지 않으면 시간 초과가 발생하고,
출력 시 endl
가 아닌 \n
을 사용하지 않으면 시간 초과가 발생한다.
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
구간 합 구하기 5 출처 : 11660번: 구간 합 구하기 5 (acmicpc.net)
구간 합 구하기 5 문제는 구간 합 구하기 4 문제를 1차원에서 2차원으로 확장시킨 문제이다.
나의 풀이 :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
vector<vector<int>>dp(N+1, vector<int>(N+1, 0));
for (int i =1;i<=N;i++)
for (int j = 1; j <= N; j++)
{
int num;
cin >> num;
dp[i][j] = dp[i][j - 1] + num;
}
for (int i = 0; i < M; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int result = 0;
for (int j = x1; j <= x2; j++)
result += (dp[j][y2] - dp[j][y1 - 1]);
cout << result << '\n';
}
return 0;
}
728x90