C++:: boj 1025 < 제곱수 찾기>

등차수만큼 거리가 있는 부분들을 고른다는 부분에서 헷갈릴 수 있지만 간단하게 예시를 들면 현재위치에서 오른쪽으로 2칸 아래로 1칸 의 수들을 연속으로 고를 수 있다는 소리이다.

풀다보면 감은 오는데 어떻게 구현할지 뇌정지가 오는 문제였다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> res;
int n, m, answer = -1;

void getNums(int x, int y, int dx, int dy, vector<string>& board) {
// x,y에서 dx dy 만큼 떨어진 거리의 숫자들을 채택
	string num;
	if (!dx && !dy) {// 예외 케이스
		res.push_back(board[x][y]-'0');
		return ;
	}
	for (int i=x, j=y; 0<=i&&i<n&&0<=j&&j<m; i+=dx, j+=dy) {
		num += board[i][j];
		res.push_back(stoi(num));// 만들어주는 수는 모두 넣어준다.
	}
}

int main() {
	cin >> n >> m;
	vector<string> board(n);
	for (int i=0; i<n; i++) {
		cin >> board[i];
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {// 모든 판위에서
			for (int dx=-i; dx<n-i; dx++) {//dx
				for (int dy=-j; dy<m-j; dy++) {//dy 등차를 이루는
					getNums(i, j, dx, dy, board);
				}
			}
		}
	}
	sort(res.begin(), res.end(), greater<int>());
	res.erase(unique(res.begin(), res.end()), res.end());// 중복 데이터 삭제
	for (auto r : res) {
		int sq = sqrt(r);
		if (sq*sq==r) {
			answer = r;
			break ;
		}
	}
	cout << answer << "\n";
}