✅ 백준 10986 나머지 합

문제 링크
풀이 링크

합 배열을 활용해야 한다.
합 배열은 입력받은 배열이 arr라면 합 배열 S[i]=arr[0]+arr[1]+...arr[i] 인 배열이다.

문제의 조건을 만족하려면 아래 식이 성립해야 한다.

풀이 출처의 소스 코드는 아래와 같다

import java.util.*;
import java.io.*;

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());

        // 1. N(수의 개수), M(나누기 할 수) 입력받기
        int N = Integer.parseInt(st.nextToken());   // 수의 개수
        int M = Integer.parseInt(st.nextToken());   // 나누기 할 수
        long result = 0;                            // M으로 나누어떨어지는 (i,j) 쌍의 개수
        long[] S = new long[N + 1];                 // 합배열
        long[] cnt = new long[M];                   // 같은 나머지의 인덱스를 카운트하는 배열

        // 2. N개의 수 입력받으면서 누적합을 M으로 나눈 나머지를 배열 S에 저장한다.
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            S[i] = (S[i - 1] + Integer.parseInt(st.nextToken())) % M;
            // 0~i까지의 합을 M으로 나눈 나머지가 0인 경우의 수 카운팅
            if(S[i] == 0) {
                result++;
            }
            // 나머지가 같은 인덱스의 수 카운팅
            cnt[(int) S[i]]++;
        }

        // 3. S[j] % M == S[i-1] % M 을 만족하는 (i,j)의 수를 결과값에 더한다.
        // 즉, cnt[i](i가 나머지인 인덱스의 수)에서 2가지를 뽑는 경우의 수 카운팅한다.
        for(int i=0; i<M; i++) {
            if(cnt[i] > 1) {
                result += (cnt[i]* (cnt[i]-1) / 2);
            }
        }
        System.out.println(result);
    }
}

주의할 점은 long 형을 활용하지 않으면 IndexOutOfRange 예외가 발생한다. int형의 합을 저장하는 배열이라 자칫하면 int의 범위를 넘을 수 있다

✅ 백준 25682 체스판 다시 칠하기

문제 풀이 링크
문제 링크

---

체스판 다시 칠하기 문제는 2차원 배열에 대한 누적 합, 구간 합 개념을 알아야 한다.
아래 링크에서 자세히 설명해주니 참고하자
2차원 배열 누적 합, 부분 합

누적 합
S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]

구간 합

Range(x1,y1,x2,y2) = (x1,y1)부터 (x2,y2)까지의 구간 합 
= S(x2,y2)-S(x1-1,y2)-S(x2,y1-1)+S(x1-1,y1-1)

풀이 코드

import java.util.*;
import java.io.*;

public class Main{
	
	static int N,M,K;
	static char[][] board;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		board = new char[N][M];
		String line;
		for (int i=0; i<N; i++) {
			line = br.readLine();
			for (int j=0; j<M; j++) {
				board[i][j] = line.charAt(j);
			}
		}
	
		System.out.println(Math.min(minimal_board('B'),minimal_board('W')));
		
	}
	public static int minimal_board(char color) {
		int count = Integer.MAX_VALUE;
		int value;
		int[][] prefix_sum = new int[N+1][M+1];
		for (int i=0; i<N; i++){
			for (int j=0; j<M; j++){
				if ((i+j)%2==0) value = board[i][j] != color ? 1:0;
				else value = board[i][j]==color ? 1:0;
				prefix_sum[i+1][j+1] = prefix_sum[i][j+1]+prefix_sum[i+1][j]-prefix_sum[i][j]+value;
			}
		}
		
		for (int i=1; i<=N-K+1; i++) {
			for (int j=1; j<=M-K+1; j++) {
				count = Math.min(count,prefix_sum[i+K-1][j+K-1]-prefix_sum[i+K-1][j-1]-prefix_sum[i-1][j+K-1]+prefix_sum[i-1][j-1]);
			}
		}
		return count;
	}
}