728x90
반응형
https://github.com/ROUTINE-STUDY/Algorithm
알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.
문제 출처 : https://www.acmicpc.net/problem/1018
문제 설명
풀이 방법
문제 파악 및 경우의 수 탐색은 그림, 노가다로 확인하였습니다.
코드 설명은 주석을 통해 달았습니다.
내 코드(JAVA)
public class Sanghoo {
static char[][] board;
final static int boardRowSize = 8;
final static int boardColSize = 8;
final static int boardSize = boardRowSize * boardColSize;
public static void main(String[] args) throws IOException {
int result = 2500;
try(final BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
StringTokenizer st = new StringTokenizer(br.readLine());
int inputN = Integer.parseInt(st.nextToken());
int inputM = Integer.parseInt(st.nextToken());
// 입력 받기
board = new char[inputN][];
for(int i=0; i<inputN; i++) {
board[i] = br.readLine().toCharArray();
}
/*
row는 행의 수(입력받은 개수)를 의미하고, col은 열의 수(각 입력의 인덱스)를 의미
boardRowSize 및 boardColSize - 1을 한 이유는 모든 경우의 수를 그려보던 중 규칙 발견
(i, j) = (0,0), (0,1) ... 이런식으로 자를 수 있는 보드판의 지점을 얻을 수 있음
*/
for(int i = 0; i<=inputN-boardRowSize; i++) {
for(int j = 0; j<=inputM-boardColSize; j++) {
// 자를 수 있는 보드판 경우의 수 모두 탐색
result = Math.min(result, getPaintingCount(i , j));
}
}
System.out.println(result);
}
}
// 해당 보드판에서 적게 칠하는 개수를 반환
private static int getPaintingCount(int row, int col) {
int paintingCount = 0;
for(int i = row; i<row+boardRowSize; i++) {
// 처음에는 시작점이 검정, 흰색인 케이스들까지 고려하여 모두 구하려고 했으나, 한 케이스만 구하면 그 반대는 역으로 구할 수 있음을 확인(그림 및 노가다..)
// 행별로 시작하는 color 지정(짝수는 검정, 홀수는 흰색으로 지정)
char targetColor = (i%2 == 0) ? 'B' : 'W';
for(int j = col; j<col+boardColSize; j++) { // 열의 시작점에서 원하는 보드 크기만큼 확인해야함
char curBoardColor = board[i][j];
if(targetColor != curBoardColor) ++paintingCount;
targetColor = (targetColor == 'B') ? 'W' : 'B'; // 안쪽 반복문에서 계속 targetColor를 반전시키며 진행
}
}
// 위 for문으로 검정색으로 시작할때의 개수를 구했고, 보드의 크기를 활용하여 반대의 케이스 수 구하여 더 작은 값 return
return Math.min(paintingCount, boardSize - paintingCount);
}
}
스터디 피드백 내용
for문 이해하기 쉽도록 변경
시간복잡도 계산법 리뷰 및 스터디 - https://github.com/ROUTINE-STUDY/Algorithm/pull/234
728x90
반응형
'알고리즘' 카테고리의 다른 글
[백준/JAVA] 17952. 과제는 끝나지 않아! (0) | 2022.04.04 |
---|---|
[백준/JAVA] 9094. 수학적 호기심 (0) | 2022.01.24 |
[백준/JAVA] 2309. 일곱 난쟁이 (0) | 2022.01.22 |
[백준/JAVA] 17509. And the Winner Is... Ourselves! (0) | 2021.11.02 |
[백준/JAVA] 4796. 캠핑 (0) | 2021.10.30 |
댓글