[C++] 백준 1025번: 제곱수 찾기

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

1025번: 제곱수 찾기

문제

문제 설명이 어렵게 서술돼 있다. 주어진 N x M의 격자판에서 행 번호와 열 번호가 각각 등차수열을 이루는 제곱수 중 가장 큰 값을 구하는 것이 목표다.

예를 들어, {arr[0][0], arr[1][2], arr[2][4]} 처럼 행 번호는 공차가 1인 등차수열이고 열 번호는 공차가 2인 등차수열인 경우가 있다. 이때, 각각의 수가 {1, 2, 1}일 경우 이는 제곱수이므로 후보가 될 수 있는 것이다.

풀이

1. 행 번호의 공차를 dr, 열 번호의 공차를 dc라고 정의하고 각각을 구간 [-N, N], [-M, M]에서 순회한다.

2. 각 구간에서 순회하면서 행 번호 r과 열 번호 c에 대해 구간 [0, N), [0, M)을 순회하며, 각 점을 시작점으로 하고 공차를 각각 dr, dc로 하는 제곱수를 찾는다.

3. 각 길이 마다 제곱수인지 확인 후, 제곱수라면 이전까지의 최대 제곱수 MAX보다 큰 수인지 비교하여 최대 제곱수를 최신화한다.

코드

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> arr(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M)
			arr[r][c] = line[c] - '0';
	}

	int MAX = -1;
	FOR(r, N) FOR(c, M) {
		for (int dr = -N; dr <= N; ++dr)
			for (int dc = -M; dc <= M; ++dc) {
				if (dr == 0 && dc == 0) continue;

				int _r = r, _c = c, num = -1;
				while (_r >= 0 && _r < N && _c >= 0 && _c < M) {
					if (num == -1) num = 0;
					num *= 10;
					num += arr[_r][_c];
					_r += dr;
					_c += dc;

					if (num < 0) continue;

					long double sr = sqrt(num);
					if (sr - floor(sr) == 0 && num > MAX)
						MAX = num;
				}
			}
	}

	cout << MAX << EL;

	return 0;
}