[BOJ]1660号:区間と5(Java)を求めます
2498 ワード
質問する (Silver 1)
11660号:区間と5を求めます
に答える
アイデア
やすり たんい に加える
[ ][ ][ ][ ][ ]
[][o][o]->o部分和:sum(2,5)-sum(2,2)
[][o][o]->o部分和:sum(3,5)-sum(3,2)
oの最終部分と:(sum(2,5)−sum(2,2)+(sum(3,5)−sum(3,2))
コード#コード#
package implement;
import java.util.*;
import java.io.*;
public class Main_11660_구간합구하기5 {
public static void main(String[] args) throws Exception{
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[][] map = new int[N][N];
int[][] sum = new int[N][N]; // 0,0부터 i,j까지 합 저장
for(int i =0 ; i < N ; i++){
st = new StringTokenizer(br.readLine());
for(int j =0 ; j < N ; j++){
map[i][j] = Integer.parseInt(st.nextToken());
if(i == 0 && j == 0){
sum[i][j] = map[i][j];
}
else if(j == 0){
sum[i][j] = sum[i-1][N-1]+map[i][j];
} else{
sum[i][j] = sum[i][j-1] + map[i][j];
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < M ; i++){
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken())-1;
int y1 = Integer.parseInt(st.nextToken())-1;
int x2 = Integer.parseInt(st.nextToken())-1;
int y2 = Integer.parseInt(st.nextToken())-1;
/**
* 줄 단위로 더해줌
* [ ][ ][ ][ ][ ]
* [ ][ ][o][o][ ] -> o 부분 합: sum(2,5) - sum(2,2)
* [ ][ ][o][o][ ] -> o 부분 합: sum(3,5) - sum(3,2)
* => o의 최종 부분 합: ( sum(2,5) - sum(2,2) ) + ( sum(3,5) - sum(3,2) )
*/
int partial = 0;
for(int j = x1 ; j <= x2 ; j++){
if(y1 == 0 && j == 0) partial += sum[j][y2];
else if(y1 == 0) partial += (sum[j][y2] - sum[j-1][N-1]);
else partial += (sum[j][y2]-sum[j][y1-1]);
}
sb.append(partial+"\n");
}
System.out.println(sb.toString());
}
}
Reference
この問題について([BOJ]1660号:区間と5(Java)を求めます), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ11660번-구간-합-구하기-5-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol