(C++) - 백준(BOJ) 1025 : 제곱수 찾기

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

1025번: 제곱수 찾기

brute force 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

n행 m열, 정답 변수 ans, 수가 적힌 표를 의미하는 이차원 배열 chart를 선언한 뒤 정보를 입력받습니다.ans는 -1로 초기화해줍니다. 답이 없는 경우 -1을 출력하기 위함입니다.

📔 풀이과정

뽑은 수의 행과 열좌표들을 나열했을 때 각각 행끼리는 등차수열, 각각의 열끼리도 등차수열인 수가 완전 제곱수인 모든 경우를 비교해 최댓값을 ans에 저장하면 됩니다.

총 5중 loop 문을 수행하면 됩니다.

1. 첫 2중 for문은 모든 수를 확인하기 위한 용도

2. 나머지 2중 for문은 각각 행, 열의 등차를 고정시켜서 수를 뽑기 위한 용도로 사용됩니다. 

3. 마지막 loop 문은 while문으로 결정된 등차의 (행, 열) 좌표가 유효한 경우 수를 뽑고 완전 제곱수인지 확인해주면 됩니다. 완전 제곱수라면 ans에 그 최댓값을 저장합니다.

 

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = -1, chart[10][10];

bool isSquare(int num){
    int root = (int)sqrt(num);
    return root * root == num;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) 
            scanf("%1d", &chart[i][j]);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int x = -n; x < n; x++){
                for(int y = -m; y < m; y++){
                    if(!x && !y) continue;
                    int r = i, c = j, num = 0;
                    while(0 <= r && r < n && 0 <= c && c < m){
                        num *= 10;
                        num += chart[r][c];
                        r += x, c += y;
                        if(isSquare(num)) ans = max(ans, num);
                    }
                }
            }
        }
    }
    cout << ans;
}