백준 1025 제곱수 찾기 c++

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

1025번: 제곱수 찾기

아이디어는 금방 생각 났고, 구현도 금방 했는데 디버깅이 겁나 오래걸렸다.

일단 문제를 잘못 본게 크다. x, y 증가량 즉 기울기가 무조건 양수인 줄 알았는데 아니였고

1 4

1234

이 경우에 xdist 0 ydist 1 일때

12 123 1234 다 조합에 들어가야 한다.

또 xdist, ydist가 전부 0 이라 무한루프 빠지는 것만 조심하면 된다.

지금 보니 굳이 int로 바꿔 파싱하지 않고 그냥 vector<string>으로 받아서 모든 조합에 stoi하는게 훨씬 낫겠다.

// 제곱수 찾기

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>

using namespace std;

int res = -1;
unordered_set<int> s;

void f2(int num) {
	// cout << num << endl;
	int sqrt_num = sqrt(num);
	if (sqrt_num * sqrt_num == num)
		res = max(res, num);
}

void f(const vector<int>& v) {
	for (int i = 1; i <= v.size(); i++) {
		int num = 0;
		for (int j = 0; j < i; j++)
			num = num * 10 + v[j];
		if (s.find(num) == s.end()) {
			s.insert(num);
			f2(num);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);

	int col, row;
	cin >> col >> row;
	vector<vector<int> > board(col,vector<int>(row, 0));

	for (int i = 0;i < col; i++) {
		string input;
		cin >> input;
		for (int j = 0; j < row; j++)
			board[i][j] = input[j] - '0';
	}

	for (int start_x = 0; start_x < col; start_x++) {
		for (int start_y = 0; start_y < row; start_y++) {
			for (int dist_x = -col; dist_x < col; dist_x++) { // dist 제일 작은 거부터 증가
				for (int dist_y = -row; dist_y < row; dist_y++) {
					if (dist_x == 0 && dist_y == 0) // 증가량 0 0 무한루프
						continue;
					vector<int> cur;
					for (int x = start_x, y = start_y;x >= 0 && x < col && y >= 0 && y < row; x += dist_x,y += dist_y) // 경계값 다 검사
						cur.push_back(board[x][y]);
					f(cur);
				}
			}
		}
	}
	cout << res;
}

시간 0ms 만드려고 set에 담고 제일 큰 것부터 한꺼번에 검사해봤는데 시간 차이 없었다.