CT
[BOJ] 23단계 누적 합
kinggora
2023. 5. 3. 23:56
| 1 | 11659 | 구간 합 구하기 4 |
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 reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int[] sum = new int[N + 1];
sum[0] = 0;
tokenizer = new StringTokenizer(reader.readLine());
for(int i = 1; i <= N; i++) {
sum[i] = sum[i-1] + Integer.parseInt(tokenizer.nextToken());
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {
tokenizer = new StringTokenizer(reader.readLine());
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
sb.append(sum[b] - sum[a-1]).append("\n");
}
System.out.print(sb);
}
}*입력과 동시에 이전 항의 누적 합을 이용하여 현재 항의 누적 합을 초기화한다.
*1번째 수의 누적합을 다른 누적합과 동일한 방식으로 처리하기 위해 sum 배열의 크기를 N+1로 했다.
| 2 | 2559 | 수열 |
연속적인 K개의 부분 수열의 합이 최대가 되는 값
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int K = Integer.parseInt(tokenizer.nextToken());
int[] prefixSum = new int[N + 1];
prefixSum[0] = 0;
tokenizer = new StringTokenizer(reader.readLine());
for(int i = 1; i <= N; i++) {
prefixSum[i] = prefixSum[i-1] + Integer.parseInt(tokenizer.nextToken());
}
int max = Integer.MIN_VALUE;
for(int i = K; i <= N; i++) {
max = Math.max(prefixSum[i] - prefixSum[i - K], max);
}
System.out.println(max);
}
}
| 3 | 16139 | 인간-컴퓨터 상호작용 |
| 4 | 10986 | 나머지 합 |
| 5 | 11660 | 구간 합 구하기 5 |
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 reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int[][] sum = new int[N][N + 1];
for(int i = 0; i < N; i++) {
tokenizer = new StringTokenizer(reader.readLine());
for(int j = 1 ; j <= N; j++) {
sum[i][j] = sum[i][j-1] + Integer.parseInt(tokenizer.nextToken());
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {
tokenizer = new StringTokenizer(reader.readLine());
int x1 = Integer.parseInt(tokenizer.nextToken());
int y1 = Integer.parseInt(tokenizer.nextToken());
int x2 = Integer.parseInt(tokenizer.nextToken());
int y2 = Integer.parseInt(tokenizer.nextToken());
int result = 0;
for(int j = x1 - 1; j < x2; j++) {
result += sum[j][y2] - sum[j][y1 - 1];
}
sb.append(result).append("\n");
}
System.out.print(sb);
}
}*sum[i][]: i행 별 누적합 계산
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 reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int[][] arr = new int[N + 1][N + 1];
int[][] dp = new int[N + 1][N + 1];
for(int i = 1; i <= N; i++) {
tokenizer = new StringTokenizer(reader.readLine());
for(int j = 1 ; j <= N; j++) {
arr[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
for(int i = 1; i <= N; i++) {
for(int j = 1 ; j <= N; j++) {
dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j];
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {
tokenizer = new StringTokenizer(reader.readLine());
int x1 = Integer.parseInt(tokenizer.nextToken());
int y1 = Integer.parseInt(tokenizer.nextToken());
int x2 = Integer.parseInt(tokenizer.nextToken());
int y2 = Integer.parseInt(tokenizer.nextToken());
int result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
sb.append(result).append("\n");
}
System.out.print(sb);
}
}*dp[i][j]: (1,1)부터 (i,j)까지의 누적 합 계산
| 6 | 25682 | 체스판 다시 칠하기 2 |
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 reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int K = Integer.parseInt(tokenizer.nextToken());
int[][] startW = new int[N+1][M+1];
int[][] startB = new int[N+1][M+1];
for(int i = 1; i <= N; i++) {
String str = reader.readLine();
for(int j = 1; j <= M; j++) {
if((i + j) % 2 == 0) {
if(str.charAt(j-1) == 'W') {
startB[i][j] = 1;
} else {
startW[i][j] = 1;
}
} else {
if(str.charAt(j-1) == 'W') {
startW[i][j] = 1;
} else {
startB[i][j] = 1;
}
}
}
}
int dpW[][] = new int[N+1][M+1];
int dpB[][] = new int[N+1][M+1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
dpW[i][j] = dpW[i][j-1] + dpW[i-1][j] - dpW[i-1][j-1] + startW[i][j];
dpB[i][j] = dpB[i][j-1] + dpB[i-1][j] - dpB[i-1][j-1] + startB[i][j];
}
}
int min = Integer.MAX_VALUE;
for(int i = K; i <= N; i++) {
for(int j = K; j <= M; j++) {
int w = dpW[i][j] - dpW[i][j - K] - dpW[i - K][j] + dpW[i - K][j - K];
int b = dpB[i][j] - dpB[i][j - K] - dpB[i - K][j] + dpB[i - K][j - K];
min = Math.min(Math.min(w,b), min);
}
}
System.out.println(min);
}
}