백준 [1025] 제곱 수 찾기

[youbeen2798]

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

문제

• 난이도: 골드 5

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

• 서로 다른 1개 이상의 칸을 선택할 때, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하며, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 함

• 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수 하나를 만들 수 있음

• 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구하는 문제( 완전 제곱수란 어떤 정수를 제곱한 수)

• 만약, 제곱수를 만들 수 없는 경우에는 -1을 출력

• 완전 탐색문제

• 문제를 이해하는데 시간이 오래걸리지만, 한번 이해하면 쉽게 풀리는 문제

함수 1

bool isoutOfBounds(int x, int y) { 
	if (x < 0 || x >= n || y < 0 || y >= m) { // x와 y가 n행 y열을 벗어나면
		return true; //true리턴
	}
	else { //아니라면
		return false; //false 리턴
	}
}

함수2

bool isSquare(int value) { //제곱수인지 판별하는 함수
	int sq = sqrt(value);

	if (sq * sq == value) { //루트를 씌운 정수값의 제곱이 원래 값과 같다면 제곱수
		return true;
	}
	else {
		return false;
	}
}

구현

#include <iostream>
#include <cmath>
using namespace std;

char map[10][10]; //값을 입력할 때 공백이 없으므로 문자로 입력받기

int n, m;

int answer = -1;  // 만약 제곱수가 없어 값이 갱신되지 않았다면 초기값인 -1을 출력할것임

bool isoutOfBounds(int x, int y) {
	if (x < 0 || x >= n || y < 0 || y >= m) {
		return true;
	}
	else {
		return false;
	}
}

bool isSquare(int value) {
	int sq = sqrt(value);

	if (sq * sq == value) { //루트를 씌운 정수값의 제곱이 원래 값과 같다면 제곱수
		return true;
	}
	else {
		return false;
	}
}
int main() {
	ios_base::sync_with_stdio(0); //입출력 빠르게(필수)
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}

	for (int x = 0; x < n; x++) { //숫자가 시작되는 초기 x값
		for (int y = 0; y < m; y++) { //숫자가 시작되는 초기 y값
			for (int dx = -n; dx < n; dx++) { //행의 등차수열
				for (int dy = -m; dy < m; dy++) { //열의 등차수열

					if (dx == 0 && dy == 0) { //만약 
						continue;
					}
					int value = 0;

					int curX = x; //현재 x좌표 값
					int curY = y; //현재 y좌표 값

					while (!isoutOfBounds(curX, curY)) { //xy좌표가 행렬을 벗어나지 않는다면
						value = 10 * value + (map[curX][curY] - '0'); //값 갱신 ( 12에 3을 추가하려면 {12*10 + 3 = 123}과 같은 원리 ) 

						if (isSquare(value)) {
							answer = max(value, answer); //만약 더 값이 큰 제곱수라면 교환
						}
						curX += dx; //x좌표 갱신
						curY += dy; //y좌표 갱신
					}
				}
			}
		}
	}

	cout << answer;
}

• 꿀팁이 있다면
• 숫자 = 문자 - '0';
• 문자 = 숫자 + '0'; 으로 쉽게 변환이 가능하다.

<문제 풀이 예시>
예를 들어,
n = 2, m = 3,
행렬은
123
456
이라 할 때 answer이 갱신되는 과정을 살펴보자.

예시1.
x = 0, y = 0, dx = 1, dy =2 라면,

curX = 0, curY = 0 이므로, value = 1
cur X = 1, curY = 2이므로, value = 16(제곱수)
cur X = 2, curY = 3은 행렬을 벗어나므로 while문 밖으로 나옴
--> answer = 16

예시2.
x = 1, y = 2, dx = 0, dy = -2라면,

curX = 1, curY = 2이므로, value = 6
curX = 1, curY = 0이므로, value = 64(제곱수)
curX = 1, curY = -2는 행렬 벗어남 -> while문 밖으로
--> answer = 64로 갱신

최종 결과값: 64