https://www.acmicpc.net/problem/2630
걸린 시간 : 19분 26초
기초적인 분할 정복 문제이다. 분할 정복은 재귀의 한 갈래이다.
재귀를 알 때 제일 중요한 것은 점화식이다. 점화식만 잘 파악하면 끝나는 문제.
알고리즘
색종이를 자를 cut() 메소드를 재귀호출한다. 재귀호출에 필요한 파라미터를 생각해보자.
파라미터의 조합으로 색종이를 자른 한 부분을 특정할 수 있으면 된다! 즉, 시작점이 필요하고, 색종이의 사이즈가 필요하므로 총 3개의 파라미터가 필요하다.
Base case를 살펴보자. 매 호출마다 해당 색종이가 모두 같은 색인지 확인하고 맞다면 카운트하고 return; 한다. 그렇지 않다면 종이를 네 부분으로 나눈다. 즉, 재귀호출을 4번 진행한다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ2630 {
static int N;
static int[][] board = new int[130][130];
static int whiteNum;
static int blueNum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
cut(0, 0, N);
System.out.println(whiteNum);
System.out.println(blueNum);
}
private static void cut(int ci, int cj, int n) {
if (allSame(ci, cj, n)) {
if (board[ci][cj] == 1) {
blueNum++;
} else {
whiteNum++;
}
return;
}
cut(ci, cj, n/2);
cut(ci, cj+n/2, n/2);
cut(ci+n/2, cj, n/2);
cut(ci+n/2, cj+n/2, n/2);
}
private static boolean allSame(int ci, int cj, int n) {
int tmp = board[ci][cj];
for (int i = ci; i < ci + n; i++) {
for (int j = cj; j < cj + n; j++) {
if (tmp != board[i][j])
return false;
}
}
return true;
}
}
'Baekjoon Online Judge' 카테고리의 다른 글
[BOJ] 9019 : DSLR (Java) (0) | 2023.11.09 |
---|---|
[BOJ] 14940 : 쉬운 최단거리 (Java) (0) | 2023.11.09 |
[BOJ] 1927 : 최소 힙 (Java) (0) | 2023.11.02 |
[BOJ] 11444 : 피보나치 수 6 (Java) (0) | 2023.11.02 |
[BOJ] 9251 : LCS (Java) (0) | 2023.11.02 |