[JAVA] 백준 1018 - 체스판 다시 칠하기
문제 이해
N x M 으로 되어있는 정사각형에서 체스판 8 x 8을 만들려고 한다. 체스판은 흰색과 검은색이 번갈아서 칠해져야 한다. N x M → 8 x 8 만들 때 가장 적게 칠하는 칸 수를 구하면 된다.
문제 풀이
- BufferedReader로 입력 받음
- ans(정답)을 64로 초기화 (8x8이니까 최대 칠할 칸수는 64임. 사실은 32이지만 64로 일단 초기화)
- 한칸씩 옮겨가며 8x8을 탐색한다.
- 탐색할 때 열+행이 짝수면 W, 홀수면 B로 고정시킨다.
- 지그재그로 색칠할 때 W인 것의 열+행이 짝수면 B인 것의 열+행은 홀수다.
- 짝수면 W, 홀수면 B로 고정시켜서 다시 칠해야하는 칸수를 paint라고 하자.
그렇다면, 짝수B, 홀수W로 고정시켜서 칠해야하는 칸수는 64-paint이다.
- 제일 적은 paint 값을 구하여 답을 찾는다.
코드
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));
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
char[][] square = new char[N][M];
for(int i=0;i<N;i++) {
square[i] = br.readLine().toCharArray();
}
//정답 구하기
int ans = 64;
for(int i = 0; i <= N - 8; i++) {
for(int j = 0; j <= M-8; j++) {
//해당i,j부터 8*8 탐색
int paint=0; //칠해야할 칸 수 -> 짝수 W, 홀수 B로 고정하고 계산
for(int n=0;n<8;n++) {
for(int m=0;m<8;m++) {
if((n+m)%2==0) {
if(square[i+n][j+m]!='W') paint++;
}else {
if(square[i+n][j+m]!='B') paint++;
}
}
}
paint = paint<32 ? paint : 64-paint; //칠해야할 칸 수는 paint 또는 64-paint
ans = ans<paint ? ans : paint;
}
}
System.out.println(ans);
br.close();
}
}
Author And Source
이 문제에 관하여([JAVA] 백준 1018 - 체스판 다시 칠하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@h3707/JAVA-백준-1018-체스판-다시-칠하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)