[백준]1025번 제곱수 찾기 - C/C++

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

1025번: 제곱수 찾기

문제

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

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

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

입력

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

출력

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

---

 

 N과 M의 최댓값이 9 밖에 되지 않으므로 다중 반복문을 사용해도 시간제한에 안 걸릴 확률이 높다.

 

결국 최댓값을 찾는 것이므로 조합을 전부 확인해보아야 한다.

- 2중 for 문( i , j )으로  표를 순회한다.

- 2중 for 문( dx , dy )으로 x의 증감량 , y의 증감량을 정한다.

- 1중 for 문으로 자릿수를 정한다. ( ddx , ddy )

    - ddx와 ddy는 dx와 dy로 시작하여 2자리 수부터 시작한다 (1자리 수의 경우 입력받을 때 계산하였다.)

    - 제곱수인지 확인한다.

    - 범위를 넘어가지 않는 선에서 ddx += dx , ddy += dy를 하며 자리 수를 늘려나간다.

 

5중 for문이므로 10^5 정도의 연산량으로 2초면 충분하다.

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int n,m,ans ,flag=-1;
char arr[11][11];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '9' && flag < 9) flag = 9;
			else if (arr[i][j] == '4' && flag < 4) flag = 4;
			else if (arr[i][j] == '1' && flag < 1) flag = 1;
			else if (arr[i][j] == '0' && flag < 0) flag = 0;
		}
	}
	ans = flag;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			string str;
			str += arr[i][j];
			for (int dx = -i; dx + i < n; dx++) {
				for (int dy = -j; dy + j < m; dy++) {
					if (!dx && !dy) continue;
					string s;
					s = str;
					for (int ddx = dx, ddy = dy
						;i + ddx < n && i+ddx >= 0 && j + ddy < m&& j + ddy >= 0
						; ddx += dx ,ddy += dy) {
							s += arr[i + ddx][j + ddy];
							int num = stoi(s);
							int sqnum = sqrt(num);
							if (num == sqnum * sqnum && num > ans)
								ans = num;
						
					}
				}
			}
		}
	}
	cout << ans;

}

---

    오늘은 유형 대신 레벨로 검색하여 문제를 선정하였다. 문제를 보았을 때 dfs로 풀 수도 있을 것 같았지만 다중 for문을 통해서도 풀 수 있을 것 같아 다중 for문을 사용하였다. 논리적으로는 간단하지만 for문을 여러 개 작성하는 과정이 헷갈렸다. 특히 dx , dy로 증감량을 조절하고 ddx와 ddy로 실제 i , j에 더하는 부분의 설계가 섞이면서 헷갈렸지만 결국 풀었다.

   

    일주일간 시원하게 놀다가 다시 공부하려니 손에 잘 잡히지 않는다! 저번 주말에는 '피의게임'을 보았는데 굉장히 재미있었다. 주말 동안 7편 보고 이제 4편 남았다! 더 보면서 놀고먹고 싶지만 많이 쉬었으니 열심히 공부해야겠다.