https://www.acmicpc.net/problem/1992
문제 해결 과정
착안
주어진 데이터가 0 또는 1의 값으로 균일한지 판단하고, 균일하지 않다면 주어진 데이터를 4 개의 균등한 영역으로 나눈 다음 각각의 영역이 다시 0 또는 1의 값으로 균일한지 판단하는 분할 정복(divide and conquer) 알고리즘의 코드를 작성하여 문제를 해결하고자 했다.
구현
주어진 영역이 0 또는 1의 값으로 균일한 상태인지 판단하는 함수를 구현하여 활용하였고, 분할 정복 알고리즘에 따라 결과를 출력할 때 괄호를 출력하기 위한 명령줄의 위치에 유의하여 문제를 해결하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
using namespace std;
int Data[64][64];
bool IsHomogeneous(int x, int y, int len)
{
for (int i = y; i < y + len; i++)
for (int j = x; j < x + len; j++)
if (Data[y][x] != Data[i][j])
return false;
return true;
}
void Partition(int x, int y, int len)
{
int half = len / 2;
if (IsHomogeneous(x, y, len))
cout << Data[y][x];
else
{
cout << "(";
Partition(x, y, half);
Partition(x + half, y, half);
Partition(x, y + half, half);
Partition(x + half, y + half, half);
cout << ")";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
char line[65] = { 0, };
cin >> line;
for (int j = 0; j < N; j++)
Data[i][j] = line[j] == '1' ? 1 : 0;
}
Partition(0, 0, N);
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 2156번: 포도주 시식 (0) | 2023.07.06 |
---|---|
[Baekjoon] 1780번: 종이의 개수 (0) | 2023.07.05 |
[Baekjoon] 14891번: 톱니바퀴 (0) | 2023.07.03 |
[Baekjoon] 11279번: 최대 힙 (0) | 2023.07.02 |
[Baekjoon] 10866번: 덱 (0) | 2023.07.02 |
댓글