https://www.acmicpc.net/problem/11660
문제 풀이
구간합 문제라고 생각하여 한 줄마다 누적합 배열을 만들었다.예를 들어 (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
'알고리즘' 카테고리의 다른 글
[백준] 2467번 용액 C++ 문제풀이 (1) | 2024.01.08 |
---|---|
[백준] 14502번 연구소 C++ 문제풀이 (0) | 2024.01.08 |
[백준] 15650번 N과 M C++ 문제풀이 (1) | 2024.01.01 |
[백준] 1629번 곱셈 C++ 문제풀이 (0) | 2023.12.30 |
[백준] 1932번 정수 삼각형 C++ 문제풀이 (0) | 2023.12.29 |