백준 1025번, 제곱수 찾기

백준 1025번 c언어 문제풀이

문제: N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.

연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로
등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

풀이:

이 문제를 풀기 위해선 두가지를 할 수 있어야 한다.

1. 완전 제곱수인지 판별 할수 있어야 한다.
2. brute force 알고리즘이므로 일일이 조건에 맞는 숫자를 만들어야 한다.

2번을 할때 가장 힘들었다. 그 이유는 모든 경우를 만족하는 반복문을 만들기 힘들었기 때문이다.
4개의 for문과 하나의 while문을 사용해 답을 구할 수 있었다.
나머지 풀이는 코드의 주석으로 달아놓겠다.

코드:

#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

int main(){

    int n, m;
    int arr[9][9];
    int max = -1; //-1로 초기화한 이유는 결과가 없을 때 -1을 출력하기 위함
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&arr[i][j]);       //공백없이 숫자 입력 받아서 숫자 하나씩 배열에 저장하기
        }
    }

    //모든 등차수열을 판별해야한다. f(n) = f(n-1) + a
    //예를 들어 표가 3*3이면, (1,1)경우, (1,1),(1,2)경우,(1,1),(2,1) 경우, 반대 순서로 가는 경우 등차가 마이너스인 경우도 고려해야한다.
   
    for(int i=0; i<n; i++){ //처음 두 for문은 표의 모든 좌표에서 시작하기 위해
    for(int j=0; j<m; j++){
        for(int x=-n; x<n; x++){//행의 등차
            for(int y=-m; y<m; y++){//열의 등차
            if(x == 0 && y==0){
                continue; //등차가 0이면 움직이지 않으니 무한루프를 돈다.
            }
            int a = i; //0부터 시작. 처음 for문에서 i=0부터 시작하기에..
            int b = j; //-->(0,0)부터 시작
            int result = 0;
            int sq = 0;
            while(a>=0 && a<n && b>=0 && b<m){
                result = result * 10; 
                result = result + arr[a][b]; //이 줄과 윗줄은 숫자를 이어붙이는 과정이다.
                sq = (int)sqrt(result); //제곱근 구하기
                if(result == (sq * sq)){ //제곱근을 제곱한 것과 result의 값이 같으면 max에 그 값을 넣어준다.
                    if(result > max){
                        max = result;
                    }
                }

                a = a+x; //등차만큼 표 이동.
                b = b+y; 
            }  
            
            }
        }
    }
    }

    cout << max;

    return 0;
}

감사합니다. 질문있으면 댓글 부탁드립니당ㅎ