티스토리 뷰
728x90
반응형
문제 요약
- 알고리즘 분류: 구간합, 누적합, 수학
- 난이도: Silver1
- 문제내용:
- 2차원 배열을 주고 (x1, y1) ~ (x2, y2)의 합을 구해
- 사이트 : https://www.acmicpc.net/problem/11660
문제풀이
이번문제는 2차원 배열의 누적합의 기본 문제이다. 누적합, 구간합에 대한 설명은 밑에 사이트에 참조하면된다. 밑에 사이트에 2차원 배열 누적합, 구간합을 이해하고 예제 코드에서 몇개만 추가만 하면되기때문에 따로 설명을 안한다.
https://jih3508.tistory.com/50
Code
Python
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
matrix = [[0] * (N + 1)]
for _ in range(N):
matrix.append([0] + list(map(int, input().split())))
prefix_sum = [[0] * (N + 1) for _ in range(N + 1) ]
for i in range(1, N + 1):
for j in range(1, N + 1):
prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] + matrix[i][j] - prefix_sum[i - 1][j - 1]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
print(prefix_sum[x2][y2] + prefix_sum[x1 -1][y1 -1] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2])
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] matrix = new int[N + 1][N + 1];
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= N; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] prefix_sum = new int[N + 1][N + 1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] + matrix[i][j] - prefix_sum[i - 1][j - 1];
}
}
int x1, y1, x2, y2;
while(M-- > 0) {
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
System.out.println(prefix_sum[x2][y2] + prefix_sum[x1 -1][y1 -1] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2]);
}
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[BAEKJOON] 2587 대표값2 (0) | 2022.11.12 |
---|---|
[BAEKJOON] 10986 나머지 합 (2) | 2022.11.11 |
[BAEKJOON] 2566 최댓값 (0) | 2022.11.09 |
[BAEKJOON] 16139 인간-컴퓨터 상호작용 (0) | 2022.11.09 |
[BAEKJOON] 2559 수열 (0) | 2022.11.08 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 알고리즘
- 수학
- 그래프
- 조합
- 누적합
- 백준
- spring-boot
- 구현
- level2
- 백트레킹
- 넓이 우선 탐색
- BFS
- Programmerse
- JSCODE
- LeetCode
- 동적 계획법
- DP
- 자바
- 동적계획법
- 배열
- 파이썬
- 재귀호출
- Greedy
- java
- DFS
- 이론
- 그리디
- BaekJoon
- Python
- 문자열
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함