[백준/BOJ] 1025 제곱수 찾기

문제 : 1025 제곱수 찾기

1025번: 제곱수 찾기

각 좌표의 위치가 등차수열을 이루도록 해야 하므로

시작 위치를 정한 다음에 좌표를 옮겨가면서 이어 붙인 정수가 제곱수인지 확인해보고

최댓값을 갱신해 출력해주면 된다.

 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, ans=-1;
string arr[15];
ll f(ll x, ll y){
    ll ret=-1;
    for (int i=-9;i<=9;i++){
        for (int j=-9;j<=9;j++){
            ll chk=0;
            for (int k=0;k<=9;k++){
                if (x+i*k<0 || x+i*k>=N || y+j*k<0 || y+j*k>=M)
                    break;
                chk*=10;
                chk+=arr[x+i*k][y+j*k]-'0';
                if (sqrt(chk)==(ll)sqrt(chk)) // 제곱수인지 확인
                    ret=max(ret,chk);
            }
        }
    }
    return ret;
}
int main(){
    cin >> N >> M;
    for (int i=0;i<N;i++)
        cin >> arr[i];
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++)
            ans=max(ans,f(i,j)); // 시작좌표
    }
    cout << ans;
    return 0;
}