[백준] 1025 :: 제곱수 찾기

www.acmicpc.net/problem/1025

1025번: 제곱수 찾기

문제 :

문제 설명 세상 난해해..

자, 차분히 이해를 해 봅시다.

 

문제를 읽어보면 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열 이라는 문구가 나옵니다.

이게 무슨 뜻이냐 하면

map[i][j] 이렇게 있을 때 (i,j)의 숫자를 뽑는겁니다. 차례로 (x1,y1) , (x2,y2) , (x3, y3) 뭐이런식으로 뽑아 나가겠죠.

이때 x를 나열했을 때도 등차수열, y를 나열했을 때도 등차 수열이 되야 합니다. 

예를들어, (1,1) (1,2) ,(1,3)은 조건을 만족합니다. X의 등차가 0, Y의 등차가 1이기 때문이죠. (등차라는 용어가 맞나..? 졸업한지 너무오래되서 수열 용어 기억이 안남 ㅠ)

다른 예로, (1,1) (1,0) 도 조건을 만족합니다. X의 등차가 0, Y의 등차가 -1입니다.

반면, (1,1) (1,2) , (1,0) 이런건 안됩니다.

 

문제의 예시

2 3

123

456

 

의 경우 64가 정답인데, (2,3) , (2,1)을 뽑으면 됩니다. (저는 이해의 편의를 위해 칸의 시작을 1부터 세었습니다)

 

 

풀이 :

문제를 풀기 위해 구현해야 할 것은 크게 두개가 있습니다.

1) 제곱수를 판별하는 함수

2) 모든 칸에 대해 모든 행,열의 등차 값에 대한 완전 탐색 로직

 

 

1)제곱수 판별 함수

이거는 언어마다 구현하는 방법이 꽤 다를 것 같은데, 저는 C++을 사용하였고 그냥 간단하게 

(int)sqrt(n) 을 root 값(제곱근값)으로 잡고 , root*root를 하였을 때 원래 값이 나오면 제곱수로 판단하였습니다.

 

2) 모든 칸에 대해 모든 행, 열의 등차 값에 대한 완전 탐색

이게 문제인데, 4차 포문을 돌리면 됩니다.

1~N , 1~M까지 모든 칸에 대해(2차 포문)

등차 값 최소 -N ~ N , -M ~ M (2차포문) 이렇게 계산을 돌리면 됩니다.

 

여기까지 로직이 완벽했는데 제가 엄청 여러번 틀린 이유가 있었습니다.

이유는 바로, 등차 값으로 수열을 만들어 나갈 때 수열의 끝까지 모두 이어 붙인 후 제곱근 판별을 하면 안되는 것이었습니다.

예를들어, (1,1) (1,2), (1,3) 이렇게 수열이 완성된다 쳐도, 우리는 (1,1)일 때 검사, (1,1),(1,2)일때도 검사 , (1,1),(1,2),(1,3)일 때도 검사 이렇게 해야하는 겁니다 ㅠㅠ

정말 많이 해맸네요

 

[소스코드]

 

#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;
 
int n, m;
int ans = -1;
bool flag = false;
int arr[10][10];
bool isSqureNumber(int n) {
    int root = (int)sqrt(n);
    if (root * root == n) return true;
    else return false;
}
int main() {
    cin >> n >> m;
    string tmp = "";
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = (int)tmp[j-1]-48;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int x = -n; x < n ; x++) {//행의 등차 값
                for (int y = -m; y < m; y++) {//열의 등차 값
                    if (x == 0 && y == 0) continue;
                    int a = i, b = j;
                    int now = 0;
                    while (a > 0 && a <= n && b > 0 && b <= m) {
                        now *= 10;
                        now += arr[a][b];
                        if (isSqureNumber(now)) ans = max(ans, now);
                        a += x;
                        b += y;
                    }
                    if (isSqureNumber(now)) ans = max(ans, now);
                }
            }
        }
    }
    cout << ans << endl;
}