์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- ์ด๋ถ ํ์
- error
- ์คํ
- DP
- GCP
- ๋ฐฑํธ๋ํน
- ๋ถํ ์ ๋ณต
- ์ฐ์ ์์ ํ
- ๋ฐ์ดํฌ์คํธ๋ผ
- ๊ตฌํ
- thymeleaf
- ๋งต
- java
- web
- JPA
- ์์ ์ ๋ ฌ
- Spring
- ์ต๋จ ๊ฒฝ๋ก
- c++
- CVE
- ๊ทธ๋ฆฌ๋
- dynamic debugging
- ์๋ฎฌ๋ ์ด์
- OS
- ์ฌ๊ท
- dfs
- ๋ฌธ์์ด
- ๋์ ํฉ
- Reversing
- BFS
- Today
- Total
hades
[Baekjoon] 2630๋ฒ: ์์ข ์ด ๋ง๋ค๊ธฐ ๋ณธ๋ฌธ
๐ฅ ๋ฌธ์
https://www.acmicpc.net/problem/2630
๐ ์ค๊ณ
ํ์ฌ ์์ข ์ด์ ๋ชจ๋ ์นธ์ ์์ด ๊ฐ์ง ์์ผ๋ฉด 4๋ฑ๋ถํด ๋๊ฐ๋ ๋ฌธ์ ์ด๋ค. ์ฌ๊ท๋ก ํด๊ฒฐํ ๋์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ณ์ฐํด๋ณด๋ฉด, O(2^7*2^7+2^6*2^6*2^2+2^5*2^5*2^2*2^2...)=O(2^14*8)=O(2^17)์ด๋ฏ๋ก, ์๊ฐ ์ ํ 1์ด ๋ด์ ํด๊ฒฐํ ์ ์๋ค.
์ฌ๊ทํจ์์ ์์์ ๊ณผ ํ์ฌ ์์ข ์ด์ ๋ณ์ ๊ธธ์ด๋ฅผ ์ ๋ฌํ๋ค. ์นธ์ ์์ด ํ๋๋ผ๋ ๋ค๋ฅด๋ฉด ์๋ผ์ผ ํ๊ธฐ ๋๋ฌธ์ ๋น๊ต ๋์์ ์์์ ์ ์์ผ๋ก ํ์๋ค.
ํ์ฌ ์์ข ์ด์ ๋ชจ๋ ์นธ์ ํ์ธํ๋ฉด์ ๋ค๋ฅธ ์์ ๊ฐ์ง ์นธ์ด ์๋ค๋ฉด, 4๋ฑ๋ถํ ์์ข ์ด๋ฅผ ๋ํ๋ด๋ ์ฌ๊ทํจ์๋ฅผ ์คํํ๋ค.
ํ์ฌ ์์ข ์ด์ ๋ชจ๋ ์นธ์ ํ์ธํ๋ฉด์ ๋ค๋ฅธ ์์ ๊ฐ์ง ์นธ์ด ์๋ค๋ฉด, ์์์ ์ ์๊ณผ ๋ชจ๋ ๊ฐ๋ค๋ ์๋ฏธ์ด๋ฏ๋ก, ์์์ ์ ์์ ๊ฐ์ง ์์ข ์ด ์๋ฅผ ์ฆ๊ฐ์ํจ๋ค. 0์ ํ์์, 1์ ํ๋์์ด๋ค.
๐ ํ์ด
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
vector<vector<int>> paper(128, vector<int>(128));
vector<int> result(2);
void slice(int start_x, int start_y, int length){
int color = paper[start_x][start_y];
for (int i=start_x; i<start_x+length; i++){
for (int j=start_y; j<start_y+length; j++){
if (color != paper[i][j]){
slice(start_x, start_y, length/2);
slice(start_x+length/2, start_y, length/2);
slice(start_x, start_y+length/2, length/2);
slice(start_x+length/2, start_y+length/2, length/2);
return;
}
}
}
result[color] += 1;
return;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
cin >> paper[i][j];
}
}
slice(0, 0, n);
cout << result[0] << "\n" << result[1] << "\n";
return 0;
}
๐ ๋ฉ๋ชจ
1074๋ฒ Z์ ๋น์ทํ ๋ฌธ์
'๐ PS > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 5430๋ฒ: AC (0) | 2024.07.15 |
---|---|
[Baekjoon] 2667๋ฒ: ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ (0) | 2024.07.13 |
[Baekjoon] 2606๋ฒ: ๋ฐ์ด๋ฌ์ค (0) | 2024.07.11 |
[Baekjoon] 2579๋ฒ: ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2024.07.10 |
[Baekjoon] 2178๋ฒ: ๋ฏธ๋ก ํ์ (0) | 2024.07.10 |