[백준] 11660번 구간 합 C++ 문제풀이

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

11660번: 구간 합 구하기 5

문제 풀이

구간합 문제라고 생각하여 한 줄마다 누적합 배열을 만들었다.예를 들어 (2,2)부터 (3,4) 까지의 합이면 (2,1) ~ (2,4) 까지의 누적합에 (2,1)을 빼주고,  (3,1) ~ (3,4) 까지의 누적합에 (3,1)을 빼준 뒤 더해주면 답이 나온다. 맨처음에 시간 초과가 나서 cin.tie(NULL), ios_base::sync_with_stdio(false) 를 넣어주니 정답을 맞출 수 있었다.나는 한 줄에 누적합 배열들을 만들었는데 사람들 풀이를 확인해보니 사각형으로 누적합을 만들어줬더라...확실히 내 코드보다는 다른 사람들이 작성한 코드가 더 효율적인 코드라고 생각이 된다. 암튼 내 코드는 올려두고 다른 사람이 푼 코드는 링크를 첨부하겠다.

소스 코드

#include <iostream>
using namespace std;

long long su[1025][1025] = { 0 };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
    int M, N;
	cin >> M >> N;
    
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= M; j++) {
			int a;
			cin >> a;
			su[i][j] = su[i][j - 1] + a;
		}
	}
    
	for (int j = 0; j < N; j++) {
		int s_x, s_y, e_x, e_y;
		cin >> s_x >> s_y >> e_x >> e_y;
		int min_y = min(s_y, e_y);
		int max_y = max(s_y, e_y);
		int result = 0;
		for (int i = min(s_x, e_x); i <= max(s_x, e_x); i++) {
			result += (su[i][max_y] - su[i][min_y - 1]);
		}
		cout << result << '\n';
	}
}

다른 분들의 코드

https://hagisilecoding.tistory.com/123

백준 11660 구간 합 구하기 5 c++ [컴공과고씨]