[C++] 백준1025. 제곱수 찾기

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

1025번: 제곱수 찾기

 

블로그에 풀이가 중복되면 리뷰하지 않는데, 다른 블로그 풀이를 봐도 이해하기 좀 힘들었다

 

이해하기 힘들었던 이유는 이 문제가 반복문 5개를 만들어야 되서 그렇다. 내 머리로는 범위 설정이 너무 헷갈렸다.

풀이는 바로 떠올랐는데, 반복문을 못 만들어서 한참걸렸다.

 

 

---

 

문제 풀이방법은 배열의 각 값마다 행,열로 등차수열 할 수 있는 최대치까지 붙여가면서 제곱수인지 판단하는 방법이다.

 

예를 들자면 배열의 크기가 9x9 라고 하고, 내가 지금 탐색하는 위치가 (3,4) 라고 하자.

다음과 같이 완전탐색을 하면 된다.

 

예를 들자면 배열의 크기가 9x9 라고 하고, 내가 지금 탐색하는 위치가 (3,4) 라고 하자.
다음과 같이 완전탐색을 하면 된다.

행이 증가(감소)하지 않는다. 열이 1 증가한다.
3,4  +  3,5 + 3,6 ... +3,9 까지 + 될 때마다 제곱수인지 체크한다.

행이 증가(감소)하지 않는다. 열이 2 증가한다.
3,4 + 3,6 + 3,7...

행이 증가하지 않는다. 열이 .. 증가한다.

한 후에,

행이 1 증가(감소)한다. 열이 1~k 증가(감소)한다.
-> 증가 : 3,4 + 4,5 + 5,6 ...
-> 감소 : 3,4 + 2,5 + 1,6... 

행이 2..k' 증가(감소)한다. 열이 1~k 증가(감소)한다.

 

이런 식으로 모든 경우를 체크하자고 마음먹었다. 이해가 되지않는다면 다른 블로그를 보는 것을 추천한다.  

이 문제는 풀이가 다 비슷해서 설명을 잘 해주는 블로그를 보는게 더 도움이 잘된다.

 

배열이 9*9가 최대라서 충분히 모든 경우를 다 탐색해도 괜찮을거라 생각했고, 코드를 작성하는데 범위가 너무 헷갈리기 시작했다.  x가 1증가할때  y가 1~k증가하거나 감소하고... 

 

그렇게 한참을 범위잡는데 시간을 버리다가, 방법을 바꾸기로 했다.

 

 

---

 

 

그냥 직관적인 함수로 만들어서 돌려보자. 그리고 세부 반복문은 나중에 생각하자. 그래서 만든 함수가 아래 함수이다.

 

void FSQ(int x, int y) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (i == 0 && j == 0)
				continue;
			AF(x,y,i, j);
		}
	}
}

 

i 는 x의 증가량 (감소량) 이고, j는 y의 증가량 ( 감소량 ) 이다.  x,y 는 좌표이다.

좌표 x,y를 받아서 x,y 에 대해 (0,0) 증가(감소)  ~ (9,9) 증가(감소) 까지 싹 돌리겠다. 라는 의미로 만들었다.

 

그리고 너무 많이 증가(감소) 시켜서 배열의 범위 ( 0 이상 n,m 미만 ) 를 벗어나면 어떡하지? 라는 문제는 AF 함수에서 그냥 따로 생각하기로 했다.

 

void AF(int x, int y, int dx, int dy) {
	string s;
	s += maps[x][y];

	int mx = x;
	int my = y;

	string s2 = s;
	while (1) {
		mx += dx;
		my += dy;

		if (mx >= n || my >= m)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx -= dx;
		my -= dy;

		if (mx < 0 || my < 0)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx += dx;
		my -= dy;

		if (mx >= n || my < 0)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx -= dx;
		my += dy;

		if (mx < 0 || my >= m)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}
}

 

고려해야 될 것은 4가지 경우이다.

1. x가 변화량 ( dx ) 만큼 증가, y가 변화량 ( dy ) 만큼 증가.

1. x가 변화량 ( dx ) 만큼 증가, y가 변화량 ( dy ) 만큼 감소.

1. x가 변화량 ( dx ) 만큼 감소, y가 변화량 ( dy ) 만큼 증가.

1. x가 변화량 ( dx ) 만큼 감소, y가 변화량 ( dy ) 만큼 감소.

 

한 반복문이 끝날때마다 mx,my를 계속 x,y 로 초기화하고, 처음 좌표 maps[x][y] 를 담는 s2 도 계속 초기화해줬다.

isSQ 함수는 제곱수인지 판단해서 내가 여태까지 얻은 정답보다 크면 갱신해주는 함수이다.

 

원래 4중 for문 만들려고 했을 때 고생한 것 중 하나가 어떻게 증가와 감소를 동시에 따지고 범위 밖으로 나가면 체크 안하게 해야되지? 였다. 

(3,4) 가 같은 증감량으로 (0,0) 까지 가는 반복과 (9,9) 까지 가는 반복횟수는 다르기 때문이었다.

 

결과적으로 완성한 코드는 다음과 같다.

 

#include <iostream>
#include <map>
#include <string>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

map <string,int> pn;
char maps[10][10];
int n, m;
int ans = -1;

void isSQ(string s) {
	if (pn.count(s)) {
		if (pn[s] > ans)
			ans = pn[s];
	}
}

void AF(int x, int y, int dx, int dy) {
	string s;
	s += maps[x][y];

	int mx = x;
	int my = y;

	string s2 = s;
	while (1) {
		mx += dx;
		my += dy;

		if (mx >= n || my >= m)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx -= dx;
		my -= dy;

		if (mx < 0 || my < 0)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx += dx;
		my -= dy;

		if (mx >= n || my < 0)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}

	mx = x;
	my = y;
	s2 = s;

	while (1) {
		mx -= dx;
		my += dy;

		if (mx < 0 || my >= m)
			break;
		s2 += maps[mx][my];
		isSQ(s2);
	}
}

void FSQ(int x, int y) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (i == 0 && j == 0)
				continue;
			AF(x,y,i, j);
		}
	}
}


int main() {
	fastio;

	char c;
	cin >> n >> m;

	for (int i = 0; i * i < 1000000000; i++) {
		string s = to_string(i * i);
		pn[s] = i*i;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
			int temp = maps[i][j] -'0';
			if (( temp == 0 || temp == 1 || temp == 4 || temp == 9 ) && (temp >ans) )
				ans = temp;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			FSQ(i, j);
		}
	}

	cout << ans;

}

 

제곱수 판단은 sqrt 한 값을 다시 제곱해서 같은지 비교하면 되는데, 멍청하게 map을 썼다. 덕분에 시간도 12ms 나 찍혔다.

FSQ -> AF 로 이어지는 함수는 각 배열값 하나는 검사하지 않기 때문에, 그건 입력받을 때 temp 를 이용해 따로 처리했다.

 

 

---

결론

 

 

 

1. 제곱수 판단하기

int x = (int)sqrt(n);
if ( x*x == n ) -> 제곱수
else -> 제곱수 아님

 

 

2. 모자란 PS 실력으로 4중 5중 for문 범위까지 고려해가면서 만드는 미련한 짓을 하지 말자

-> 최대한 단순한 개념의 함수로 여러개 만들자.

 

한 20분 끄적이면서 이거 for문 4개 돌리면 될거같다 라는 생각은 들긴했다. 100% 확신도 했는데 만들기가 쉽지 않았다.

실력도 안되고 머리도 안되면서 한번에 for문 4개를 짜려고 해서 1시간 30분 날렸다.

 

시간 다 갖다 버리고도 범위를 못잡아서 아래처럼 생각하고 코드 작성하니까 10분만에 풀었다.

 

• FSQ 함수 만들기

1. ( x좌표, y좌표, x변화량, y변화량) 을 받는 함수를 만들자. 

2. 9*9 배열이니까 변화량이 아무리 커도 최대치는 8이다. 

3. 그러므로 변화량을 0~8까지 다 집어넣고 배열 범위 밖으로 넘어가는건 다음 함수에서 따로 생각하고 여기선 생각하지 말자

 

• AF 함수 만들기

1. x가 n을 안넘을 때까지 .. 식으로 범위를 잡으면 더 헷갈릴거 같다.

2. 무한반복문으로 만들고, x는 dx만큼  y는 dy만큼 계속 변하게 한 뒤에 범위 넘어가면 break 하자.

3. 한 번에 증가 감소를 둘 다 생각하지 말고 반복문 4개 만들어서 각각 break 따로 하자.