https://www.acmicpc.net/problem/1780
๋ฌธ์
N×Nํฌ๊ธฐ์ ํ๋ ฌ๋ก ํํ๋๋ ์ข ์ด๊ฐ ์๋ค. ์ข ์ด์ ๊ฐ ์นธ์๋ -1, 0, 1 ์ค ํ๋๊ฐ ์ ์ฅ๋์ด ์๋ค. ์ฐ๋ฆฌ๋ ์ด ํ๋ ฌ์ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ผ ์ ์ ํ ํฌ๊ธฐ๋ก ์๋ฅด๋ ค๊ณ ํ๋ค.
- ๋ง์ฝ ์ข ์ด๊ฐ ๋ชจ๋ ๊ฐ์ ์๋ก ๋์ด ์๋ค๋ฉด ์ด ์ข ์ด๋ฅผ ๊ทธ๋๋ก ์ฌ์ฉํ๋ค.
- (1)์ด ์๋ ๊ฒฝ์ฐ์๋ ์ข ์ด๋ฅผ ๊ฐ์ ํฌ๊ธฐ์ ์ข ์ด 9๊ฐ๋ก ์๋ฅด๊ณ , ๊ฐ๊ฐ์ ์๋ฆฐ ์ข ์ด์ ๋ํด์ (1)์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
์ด์ ๊ฐ์ด ์ข ์ด๋ฅผ ์๋์ ๋, -1๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์, 0์ผ๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์, 1๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์๋ฅผ ๊ตฌํด๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N(1 ≤ N ≤ 37, N์ 3k ๊ผด)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ N๊ฐ์ ์ ์๋ก ํ๋ ฌ์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ -1๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์๋ฅผ, ๋์งธ ์ค์ 0์ผ๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์๋ฅผ, ์ ์งธ ์ค์ 1๋ก๋ง ์ฑ์์ง ์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด
์ฌ๊ท๋ฅผ ์ด์ฉํ์ฌ ํ์๋ค
1. n*n ํฌ๊ธฐ๋งํผ ์ ์ฒด ๊ฒ์ฌํ๋ฉด์
2. ํ๊ฐ์ ์ข ์ด๋ผ๊ณ ํ๋จ์ด ๋๋ฉด (checkํจ์) ํด๋น ์ข ์ด๋ฅผ ์นด์ดํธ ํ ๋ฆฌํด
3. (n/3)*(n/3) ํฌ๊ธฐ๋งํผ ์ ์ฒด ๊ฒ์ฌ (1๋ฒ์ผ๋ก ๋์๊ฐ๊ธฐ)
์ฌ๊ท์์ฒด๋ฅผ ์๊ฐํ๋๊ฒ ์ด์ง.. ์ด๋ ต๊ธด ํ์ง๋ง
๊ทธ๋๋ ์ฌ๊ท์ ์ต์ํ๋ค๋ฉด ๊ทธ๋ญ์ ๋ญ ํ ์ ์๋ ๋ฌธ์
(๋ฌผ๋ก ๋๋ ์ฌ๊ท ์ด๋ ต๋ค)
// Authored by : seondal
// Co-authored by : -
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int N;
int paper[2190][2190]; //3^7 = 2187
int cnt[3]; // -1์ข
์ด ๊ฐฏ์, 0์ข
์ด ๊ฐฏ์, 1์ข
์ด ๊ฐฏ์
bool check(int n, int x, int y) { // (x,y) ๋ถํฐ n๊ฐ ํฌ๊ธฐ ์ข
์ด๊ฐ ๊ฐ์ ์ซ์๋ก ์ฑ์์ก๋์ง ํ์ธ
for(int i=x; i<x+n; i++)
for(int j=y; j<y+n; j++)
if(paper[i][j] != paper[x][y])
return false;
return true;
}
void recur(int n, int x, int y) {
if(check(n,x,y)) {
cnt[paper[x][y] + 1]++;
return;
}
int next = n/3;
for(int i=x; i < x + 3*next; i = i + next)
for(int j=y; j < y + 3*next; j = j + next)
recur(next, i, j);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// ์ด๊ธฐํ
cnt[0] = 0; cnt[1] = 0; cnt[2] = 0;
// ์
๋ ฅ
cin >> N;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
cin >> paper[i][j];
// ์ฌ๊ท
recur(N, 0, 0);
//์ถ๋ ฅ
cout << cnt[0] << "\n" << cnt[1] << "\n" << cnt[2];
return 0;
}
/*
*/
'๐ Baaaaaarking > 0x0B๊ฐ - ์ฌ๊ท' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ S1] ๋ฐฑ์ค 1992๋ฒ: ์ฟผ๋ํธ๋ฆฌ (83%) (0) | 2022.05.22 |
---|---|
[BOJ S3] 2603๋ฒ: ์์ข ์ด ๋ง๋ค๊ธฐ (0) | 2022.05.22 |
[BOJ S5] ๋ฐฑ์ค 17478๋ฒ: ์ฌ๊ทํจ์๊ฐ ๋ญ๊ฐ์? (0) | 2022.05.17 |
[BOJ S1][C++] ๋ฐฑ์ค 11729๋ฒ: ํ๋ ธ์ด ํ ์ด๋ ์์ (0) | 2022.05.11 |
[BOJ S1][C++] ๋ฐฑ์ค 1629๋ฒ: ๊ณฑ์ (0) | 2022.05.04 |