2630 JAVA ์์ข ์ด ๋ง๋ค๊ธฐ
๐ ๋ฌธ์
์๋ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ์ฌ๋ฌ๊ฐ์ ์ ์ฌ๊ฐํ์นธ๋ค๋ก ์ด๋ฃจ์ด์ง ์ ์ฌ๊ฐํ ๋ชจ์์ ์ข ์ด๊ฐ ์ฃผ์ด์ ธ ์๊ณ , ๊ฐ ์ ์ฌ๊ฐํ๋ค์ ํ์์์ผ๋ก ์น ํด์ ธ ์๊ฑฐ๋ ํ๋์์ผ๋ก ์น ํด์ ธ ์๋ค. ์ฃผ์ด์ง ์ข ์ด๋ฅผ ์ผ์ ํ ๊ท์น์ ๋ฐ๋ผ ์๋ผ์ ๋ค์ํ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง ์ ์ฌ๊ฐํ ๋ชจ์์ ํ์์ ๋๋ ํ๋์ ์์ข ์ด๋ฅผ ๋ง๋ค๋ ค๊ณ ํ๋ค.
์ ์ฒด ์ข
์ด์ ํฌ๊ธฐ๊ฐ N×N(N=2k, k๋ 1 ์ด์ 7 ์ดํ์ ์์ฐ์) ์ด๋ผ๋ฉด ์ข
์ด๋ฅผ ์๋ฅด๋ ๊ท์น์ ๋ค์๊ณผ ๊ฐ๋ค.
์ ์ฒด ์ข ์ด๊ฐ ๋ชจ๋ ๊ฐ์ ์์ผ๋ก ์น ํด์ ธ ์์ง ์์ผ๋ฉด ๊ฐ๋ก์ ์ธ๋ก๋ก ์ค๊ฐ ๋ถ๋ถ์ ์๋ผ์ <๊ทธ๋ฆผ 2>์ I, II, III, IV์ ๊ฐ์ด ๋๊ฐ์ ํฌ๊ธฐ์ ๋ค ๊ฐ์ N/2 × N/2์์ข ์ด๋ก ๋๋๋ค. ๋๋์ด์ง ์ข ์ด I, II, III, IV ๊ฐ๊ฐ์ ๋ํด์๋ ์์์์ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ชจ๋ ๊ฐ์ ์์ผ๋ก ์น ํด์ ธ ์์ง ์์ผ๋ฉด ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๋๊ฐ์ ํฌ๊ธฐ์ ๋ค ๊ฐ์ ์์ข ์ด๋ก ๋๋๋ค. ์ด์ ๊ฐ์ ๊ณผ์ ์ ์๋ผ์ง ์ข ์ด๊ฐ ๋ชจ๋ ํ์์ ๋๋ ๋ชจ๋ ํ๋์์ผ๋ก ์น ํด์ ธ ์๊ฑฐ๋, ํ๋์ ์ ์ฌ๊ฐํ ์นธ์ด ๋์ด ๋ ์ด์ ์๋ฅผ ์ ์์ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
์์ ๊ฐ์ ๊ท์น์ ๋ฐ๋ผ ์๋์ ๋ <๊ทธ๋ฆผ 3>์ <๊ทธ๋ฆผ 1>์ ์ข ์ด๋ฅผ ์ฒ์ ๋๋ ํ์ ์ํ๋ฅผ, <๊ทธ๋ฆผ 4>๋ ๋ ๋ฒ์งธ ๋๋ ํ์ ์ํ๋ฅผ, <๊ทธ๋ฆผ 5>๋ ์ต์ข ์ ์ผ๋ก ๋ง๋ค์ด์ง ๋ค์ํ ํฌ๊ธฐ์ 9์ฅ์ ํ์์ ์์ข ์ด์ 7์ฅ์ ํ๋์ ์์ข ์ด๋ฅผ ๋ณด์ฌ์ฃผ๊ณ ์๋ค.
์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์ข
์ด์ ํ ๋ณ์ ๊ธธ์ด N๊ณผ ๊ฐ ์ ์ฌ๊ฐํ์นธ์ ์(ํ์์ ๋๋ ํ๋์)์ด ์ฃผ์ด์ง ๋ ์๋ผ์ง ํ์์ ์์ข
์ด์ ํ๋์ ์์ข
์ด์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐ ์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ข ์ด์ ํ ๋ณ์ ๊ธธ์ด N์ด ์ฃผ์ด์ ธ ์๋ค. N์ 2, 4, 8, 16, 32, 64, 128 ์ค ํ๋์ด๋ค. ์์ข ์ด์ ๊ฐ ๊ฐ๋ก์ค์ ์ ์ฌ๊ฐํ์นธ๋ค์ ์์ด ์์ค๋ถํฐ ์ฐจ๋ก๋ก ๋์งธ ์ค๋ถํฐ ๋ง์ง๋ง ์ค๊น์ง ์ฃผ์ด์ง๋ค. ํ์์์ผ๋ก ์น ํด์ง ์นธ์ 0, ํ๋์์ผ๋ก ์น ํด์ง ์นธ์ 1๋ก ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ซ์ ์ฌ์ด์๋ ๋น์นธ์ด ํ๋์ฉ ์๋ค.
๐ ์ถ๋ ฅ
์ฒซ์งธ ์ค์๋ ์๋ผ์ง ํ์์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๊ณ , ๋์งธ ์ค์๋ ํ๋์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ ์์
์์ ์ ๋ ฅ
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
์์ ์ถ๋ ฅ
9
7
๐ ์ฑ๊ณต ๊ณผ์
์ ๊ทผํ๊ธฐ ์ด๋ ค์ ๋ ํผ๋ฐ์ค๋ฅผ ์ฐพ์๋ณด๋ฉฐ ๋ฌธ์ ๋ฅผ ์ ๊ทผํ๋ค.
๋ฌธ์ ์ ๊ทผ
์์ข
์ด๊ฐ ํ๋์ ์์ผ๋ก ์ด๋ฃจ์ด ์์ง ์๋ค๊ณ ํ๋จ์ด ๋๋ฉด ๋ฐ์ผ๋ก ์ ๊ณ , ๋ค์ํ์ธํ๊ณ ๋ฐ์ผ๋ก ์ ๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
๋ฐ๋ณต์ ์ธ ๊ณผ์ ๋ค์ ํจ์๋ฅผ ์์ฑํ์ฌ ์ฌ๊ท๋ก ํธ์ถํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
๋ฐ๋ผ์
1. ํ๋์ ์(ํฐ์ or ํ๋์)์ผ๋ก ์ด๋ฃจ์ด์ ธ์๋์ง ํ์ธํ๋ ์ฝ๋
2. ๋ฐ์ผ๋ก ์ ์ด(์ฌ์ด์ฆ๋ฅผ ๋ฐ์ผ๋ก ๋๋ ) ๋ค์ ํจ์๋ฅผ ํธ์ถํ๋ ์ฝ๋
๋ก ๋๋ ์ ์๋ค.
์ฑ๊ณต ์ฝ๋
import java.io.*;
import java.util.*;
public class Main{
public static int[][] arrays;
public static int white = 0;
public static int blue = 0;
public static void main(String[] args) throws Exception {
// ์
๋ ฅ ๊ฐ
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Integer n = Integer.parseInt(br.readLine());
arrays = new int[n][n];
for (int i = 0; i < n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < n ; j++){
arrays[i][j] = Integer.parseInt(st.nextToken());
}
}
// ์ถ๋ ฅ ๊ฐ
partition(n, 0, 0);
System.out.println(white);
System.out.println(blue);
}
public static void partition(int n, int x, int y){
// ๊ฐ์ด ์ฑ์์ ธ ์๋ ๊ฒฝ์ฐ
if(checkColor(n, x, y)){
if(arrays[x][y] == 0) white++;
else blue++;
return;
}
// ์ฑ์์ ธ ์์ง ์์ ๊ฒฝ์ฐ
n = n / 2; // ๊ฐ์ ์ ๋ฐ์ผ๋ก ๋๋๊ธฐ
partition(n, x, y); // 4์ฌ๋ถ๋ฉด
partition(n, x + n, y); // 1์ฌ๋ถ๋ฉด
partition(n, x, y + n); // 2์ฌ๋ถ๋ฉด
partition(n, x + n, y + n); // 3์ฌ๋ถ๋ฉด
}
public static boolean checkColor(int n, int x, int y){
int check = arrays[x][y];
for(int i = x ; i < n + x; i++){
for (int j = y; j < n + y; j++){
if(arrays[i][j] != check) return false;
}
}
return true;
}
}