백준 1025 c++ "제곱수 찾기" -PlusUltraCode-

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

[필자 사고]

이 문제를 풀면서 배운 점은 등차수열일 경우 앞쪽은 생각하기 쉬운데 뒤쪽 인덱스는 어떻게 접근해야 될지 고민이였다.

for(int dr = -N; dr<=N; dr++) 와 같은 for문을 작성하게 되면 모든 변경되는 부분 idx 등차수열 접근이 가능해진다. 

이 부분이 정말 재미있었다. 

또한 완전 제곱수 판단할때 sqrt(x) 값은 소숫점이 있으면 같이 double 형태로 반환하지만. 

내가 long long 자료형을 받게 되면 소수점이 버려진다. 그러면 num*num==x 형태로 

참인지 거짓인지를 통해 완전제곱수 판단이 가능해진다.

 

아래는 자세한 코드 해설이다. 

[코드 해설]

isSquare

• 매개변수로 받은 정수 x가 완전제곱수인지 판별하는 함수입니다.
• sqrt(x)로 제곱근을 구한 뒤 정수형으로 저장합니다.
• 그 값을 다시 제곱했을 때 x와 같으면 true를 반환하고, 아니면 false를 반환합니다.

---

isInside

• 좌표 (sero, garo)가 배열의 범위 안에 있는지 확인하는 함수입니다.
• 0 ≤ sero < N 그리고 0 ≤ garo < M이면 true를, 아니면 false를 반환합니다.

---

main

1. 입력
   • N, M을 입력받고 N개의 문자열을 받아서 arr에 저장합니다.
   • arr[i][j]는 극장 좌석 문제와 달리, 이번 문제에서는 보드판의 숫자를 의미합니다.
2. 초기화
   • answer를 -1로 설정합니다. (만약 완전제곱수가 하나도 없으면 그대로 출력하기 위함)
3. 모든 시작점 탐색
   • (i, k)를 보드 위 모든 좌표로 잡고 시작합니다.
4. 모든 등차수열 방향 탐색
   • dx, dy를 각각 -N ~ N, -M ~ M까지 설정합니다.
   • (dx, dy)가 (0, 0)인 경우는 제자리라서 무시합니다.
5. 숫자 생성 과정
   • 현재 좌표 (sero, garo)에서 시작합니다.
   • 보드 범위 안에 있는 동안,
     • 지금 좌표의 숫자를 num에 이어붙여서 새로운 수를 만듭니다.
     • isSquare(num)을 통해 제곱수인지 검사하고, 맞다면 answer를 갱신합니다.
     • 좌표를 (sero + dx, garo + dy)로 이동합니다.
6. 결과 출력
   • 모든 경우를 확인한 뒤, 가장 큰 완전제곱수를 출력합니다.
   • 없으면 초기값 -1이 출력됩니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;

int N, M;
vector<string> arr;

bool isSquare(ll x) {
	ll num = sqrt(x);
	return num * num == x;
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

int main(void) {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	ll answer = -1;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			for (int dx = -N; dx <= N; dx++) {
				for (int dy = -M; dy <= M; dy++) {
					if (dx == 0 && dy == 0)continue;
					int sero = i;
					int garo = k;

					ll num = 0;

					while (isInside(sero, garo)) {
						num = num * 10 + (arr[sero][garo] - '0');
						if (isSquare(num))answer = max(answer, num);
						sero += dx;
						garo += dy;
					}
				}
			}
		}
	}
	cout << answer;
}