[1025] 제곱수 찾기

문제 링크 : https://www.acmicpc.net/problem/1025

1025 - 제곱수 찾기

본문

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

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

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

입력

첫째 줄에 $N, M$이 주어진다. 둘째 줄부터 $N$개의 줄에는 표에 적힌 숫자가 1번 행부터 $N$번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 $M$번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

출력

첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 $-1$을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

• $1 \leq N, M \leq 9$
• 표에 적힌 숫자는 $0$보다 크거나 같고, $9$보다 작거나 같다.

---

풀이

문제 설명부터 이해해보자.

표 상에서 몇개의 칸을 선택할 것인데, 선택한 칸들은 행과 열이 모두 등차수열을 이루어야한다. 즉, 선택한 칸들을 나열할 때 행의 번호가 등차수열 + 열의 번호가 등차수열이어야하고, 그 순서는 바꾸지 않고 차례대로 적어 수를 하나 만들려고 한다. 그런 수들이 여러개 나올텐데, 문제에서 원하는 답은 그 수들 중 제곱수들 중 최댓값이다.

제곱수임을 판별하는 방법은 그 정수의 정수 제곱근을 구하고, 그의 제곱이 원래 정수와 같은지를 비교한다.

그럼 표 상에서 행과 열이 모두 등차수열인 방법으로 수들을 선택할 수 있는지를 알아보아야한다. 근데 그런건 없다. 다행히 표의 크기가 9칸이니 모든 방법에 대해서 찾아보는 브루트포스 방법을 취할 수 있을 것이다. 반복문을 통해 모든 경우를 찾아보자.

한가지 고려해야할 것이 있는데, 칸들을 선택하여 수들을 만드는데 최종 완성된 수만 검사하면 안된다는 점을 알아야한다. 아직 표의 끝에 도달하지 않았음에도 선택한 수들을 이용하여 제곱수를 만들 수 있고, 그들 중 정답이 존재할 수 있기 때문이다. 칸을 선택하여 수를 만들 때마다 제곱수인지 판별하는 과정을 넣어주도록 하자.

• 참고 알고리즘 : 브루트포스

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 12

#include <math.h>  // sqrt
#include <stdio.h>

typedef long long ll;
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
    int x, y;
} ND;

#define MAX_IDX 9
char grid[MAX_IDX][MAX_IDX + 1];
int n, m;
ll retval = -1;

#define max(a, b) (((a) > (b)) ? (a) : (b))

bool isVaildPosition(ND cur) {
    return ((0 <= cur.x && cur.x < n) && (0 <= cur.y && cur.y < m));
}

bool isSquareInteger(ll x) {
    ll a = (ll)sqrt(x);
    return (a * a == x);
}
void getSubProblem(ND cur, ND move) {
    ll newInt = 0;
    while (isVaildPosition(cur) == true) {
        newInt *= 10, newInt += (grid[cur.x][cur.y] - '0');
        cur.x += move.x, cur.y += move.y;

        if (isSquareInteger(newInt) == true) {
            retval = max(retval, newInt);
        }
    }
    return;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", grid[i]);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {  // start point

            for (int k = -MAX_IDX; k <= MAX_IDX; ++k) {     // brute force
                for (int l = -MAX_IDX; l <= MAX_IDX; ++l) {
                    if (k == 0 && l == 0) {
                        continue;
                    }
                    getSubProblem((ND){i, j}, (ND){k, l});
                }
            }
        }
    }

    printf("%d", retval);
    return 0;
}

• grid[][] : 입력으로 주어진 표를 기록
• isValidPosition() : 현재 탐색중인 위치가 표 안에 존재하는지 판별하는 함수
• isSquareInteger() : 제곱수인지 판별하는 함수
• getSubProblem() : 현재 위치와 등차수열 규칙이 주어졌을 때, 만들수 있는 수들을 모두 만들어보는 함수