문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
누적합?
입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.
예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면
1 | 5 | 4 | 36 | 8 | |
누적합 | 1 | 6 | 10 | 46 | 54 |
이 문제에 핵심은
1. M×N 사각형 보드에서 K×K 정사각형으로 잘랐을 때 체스판의 보드가 되어야 합니다.
2. 보드를 잘랐을 때 체스판이 되도록 색칠할 수 있습니다.
3. 체스판은 첫 칸의 색에 따른 2가지 경우가 존재합니다.
4. 색칠하는 횟수가 가장 작은 횟수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 누적합을 구성한 뒤 체스판을 K×K으로 자르는 모든 경우를 탐색합니다.
3. 색을 칠한 최소 횟수를 결과로 출력합니다.
체스판의 2가지 경우.
첫 칸에 따라 2가지 경우로 나뉠 수 있습니다.
흰색
W | B | W |
B | W | B |
W | B | W |
검은색
B | W | B |
W | B | W |
B | W | B |
색을 칠해야 하는 경우를 배열로 표현하면 서로 반대되는 것을 확인할 수 있습니다.
예를 들어 아래와 같은 M×N보드가 존재할 때
W | W | W |
B | B | B |
W | B | W |
흰색(0 : 색칠 X, 1 : 색칠 O)
0 | 1 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
검은색(0 : 색칠 X, 1 : 색칠 O)
1 | 0 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
체크판의 경우가 2개이기 때문에 두 경우에서 색칠의 최소값을 구해야합니다.
2가지 경우를 모두 확인하는 것보다는 서로 칠하는 경우가 반대가 되는 것을 응용합니다.
예를 들어
흰색에 대해서 칠하는 경우의 최소, 최대 횟수를 구한 뒤
K×K - 최대 횟수 : 검은색의 최소 횟수
2차원 배열 누적합.
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
행 더하기
1 | 3 | 6 |
4 | 9 | 15 |
7 | 15 | 24 |
열 더하기
1 | 3 | 6 |
5 | 12 | 21 |
12 | 27 | 45 |
45(2, 2) : 1 ~ 9의 합
21(2, 1) : 1 ~ 6의 합
....
예제입력1.
1. 입력된 정보를 저장합니다.
N : 4
M : 4
K : 3
B | B | B | B |
B | B | B | B |
B | B | B | W |
B | B | W | B |
2. 누적합을 구성한 뒤 체스판을 K×K으로 자르는 모든 경우를 탐색합니다.
※저는 체스판의 첫 색을 검은색이 되는 것을 기준으로 구하였습니다.
검은색(0 : 색칠X, 1 : 색칠O)
0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
1 | 0 | 0 | 0 |
누적합 구성.
행 더하기.
0 | 1 | 1 | 2 |
1 | 1 | 2 | 2 |
0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
열 더하기.
0 | 1 | 1 | 2 |
1 | 2 | 3 | 4 |
1 | 3 | 4 | 5 |
2 | 4 | 5 | 6 |
※3×3(K = 3)으로 자르는 모든 경우 중 1가지 경우를 보여드리겠습니다.
0 | 1 | 1 | 2 |
1 | 2 | 3 | 4 |
1 | 3 | 4 | 5 |
2 | 4 | 5 | 6 |
전체의 합(6) - 자른 보드의 상단 합(2) - 자른 보드 왼쪽 합(2 - 0) = 2
[i][j]는 자른 부분의 누적합의 위치
점화식으로 표현 : board[i][j] - (board[i-K][j] + board[i][j-K] - board[i-K][j-K])
위의 경우
i = 4, j = 4
board[4][4] - (board[1][4] + board[4][1] - board[1][1])
6 - (2 + 2 - 0) = 2
3. 색을 칠한 최소 횟수를 결과로 출력합니다.
첫 칸이 검은색일 때 색을 칠하는 최대값 : 4, 최소 : 2
첫 칸이 흰색일 때 색을 칠하는 최소값 : K×K - 최대값 = 3×3 - 4 = 5
최소값 2를 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 저장하였습니다.
- StringTokenizer를 사용하여 N,M,K를 띄어쓰기 끼준 나누어 저장합니다.
- M×N 보드에서 첫 칸이 검은색으로 시작할 때 색칠 관련 정보를 저장합니다.
- 누적합을 구하기 위해서 행, 열 더하기를 진행합니다.
- K×K로 자르는 모든 경우에서 점화식을 이용하여 최대값과 최소값을 구합니다.
- 최소값과 최대값을 이용하여 시작칸이 검은색, 흰색일 때의 최소값을 비교합니다.
- 색칠하는 최소 횟수를 BufferedWriter 저장합니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
결과 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, K, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
static int[][] board; //M×N배열에 색칠 관련 배열
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new int[N+1][M+1];
//false : 검은색, true : 흰색
//첫 칸은 검은색으로 설정.
boolean color = false;
//첫 칸이 검은색일 때 칠하는 경우 저장
for(int i=1;i<=N;i++){
String str = br.readLine();
for(int j=1;j<=M;j++){
char c = str.charAt(j-1);
if(!color && c == 'W') //검은색으로 색 변경
board[i][j] = 1;
else if(color && c == 'B') //흰색으로 색 변경
board[i][j] = 1;
color = !color;
}
if(M % 2 == 0)
color = !color;
}
//누적합, 행 더하기.
for(int i=1;i<=N;i++){
int temp = board[i][1];
for(int j=2;j<=M;j++){
temp += board[i][j];
board[i][j] = temp;
}
}
//누적합, 열 더하기.
for(int i=1;i<=M;i++){
int temp = board[1][i];
for(int j=2;j<=N;j++){
temp += board[j][i];
board[j][i] = temp;
}
}
//K×K 정사각형 자르는 모든 경우 탐색
for(int i=K;i<=N;i++){
for(int j=K;j<=M;j++){
//점화식을 이용한 해당 합 구하기
int temp = board[i][j] - (board[i-K][j] + board[i][j-K] - board[i-K][j-K]);
min = Math.min(min, temp); //최소값 비교하기
max = Math.max(max, temp); //최대값 비교하기
}
}
//시작이 검은색일 때 : min
//시작이 흰색일 때 : K*K - max
int answer = Math.min(min, K*K - max); //최소 횟수 구하기
bw.write(answer + ""); //최소 횟수 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
}
'백준' 카테고리의 다른 글
[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2212번, 센서 (0) | 2022.10.29 |
---|---|
[백준] 알고리즘 분류(브루트 포스,JAVA)18111번, 마인크래프트 (0) | 2022.10.29 |
[백준] 알고리즘 분류(트리,JAVA)6416번, 트리인가? (0) | 2022.10.27 |
[백준] 알고리즘 분류(트리,JAVA)14267번, 회사 문화 1 (0) | 2022.10.25 |
[백준] 알고리즘 분류(그래프 탐색,JAVA)2583번, 영역 구하기 (0) | 2022.10.24 |
댓글