์๋ <๊ทธ๋ฆผ 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๋ก ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ซ์ ์ฌ์ด์๋ ๋น์นธ์ด ํ๋์ฉ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์๋ ์๋ผ์ง ํ์์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๊ณ , ๋์งธ ์ค์๋ ํ๋์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๊ฐ์ ๊ตฌ์ญ์ ์๋ ์์ด ๊ฐ์ง ์์ผ๋ฉด ์๋ฅด๊ณ , ์๋ฅธ ํ ์ต์ข ์ ์ผ๋ก ๋จ๋ ์กฐ๊ฐ์ ๊ฐ์๋ฅผ ์๊น๋ณ๋ก ์ธ์ ์ถ๋ ฅํ๊ธฐ
๋ถํ ์ ๋ณต
1) ๋ถํ ์ ๋ณต
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
fold(x+size*j, y+size*i, size);
}
}
import java.io.*;
public class Divide_3 {
static int arr[][];
static int white = 0, blue = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i=0; i<n; i++) {
String s[] = br.readLine().split(" ");
for(int j=0; j<n; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
fold(0,0,n);
System.out.println(white);
System.out.println(blue);
}
static void fold(int x, int y, int size) {
if(!check(x,y,size)) {
size/=2;
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
fold(x+size*j, y+size*i, size);
}
}
}
}
static boolean check(int x, int y, int size) {
for(int i=y; i<y+size; i++) {
for(int j=x; j<x+size; j++) {
if(arr[y][x] != arr[i][j])
return false;
}
}
if(arr[y][x] == 1)
blue++;
else
white++;
return true;
}
}
์ฑ๊ณต~