이미지 축소 (백준 22994)

안녕하세요. 오늘은 이미지를 축소할 거예요.

문제

https://www.acmicpc.net/problem/22994

아이디어

가로로 있는 뭉탱이의 길이의 gcd값을 gcdx, 세로로 있는 뭉탱이의 길이의 gcd값을 gcdy라고 합시다. 그러면 N/gcdy,M/gcdx가 크기가 됩니다. 이걸 구해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#define ll long long
using namespace std;

ll gcd(ll a,ll b) { return ((b) ? gcd(b, a % b) : a); }

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s[1010];

	ll N, M, i, j, cnt, gcdx = 0, gcdy = 0;
	cin >> N >> M;
	for (i = 0; i < N; i++) cin >> s[i];

	for (i = 0; i < N; i++)
	{
		cnt = 1;
		for (j = 1; j < M; j++)
		{
			if (s[i][j] == s[i][j - 1]) cnt++;
			else
			{
				gcdx = gcd(gcdx, cnt);
				cnt = 1;
			}
		}
		gcdx = gcd(gcdx, cnt);
	}
	for (j = 0; j < M; j++)
	{
		cnt = 1;
		for (i = 1; i < N; i++)
		{
			if (s[i][j] == s[i - 1][j]) cnt++;
			else
			{
				gcdy = gcd(gcdy, cnt);
				cnt = 1;
			}
		}
		gcdy = gcd(gcdy, cnt);
	}

	cout << N / gcdy << ' ' << M / gcdx << "\n";
	for (i = 0; i < N / gcdy; i++)
	{
		for (j = 0; j < M / gcdx; j++)
			cout << s[i * gcdy][j * gcdx];
		cout << "\n";
	}
}

감사합니다.