문제
지민이는 천장을 보다가 직사각형 격자판을 생각했고, 각 칸에 숫자를 한 자리씩 적어 놓았다.
수업시간이 너무 지루해서 지민이는 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열을 생각해 보았다. 그리고 나서 그 수열의 수를 모두 이어 붙였다. 이렇게 만든 수 중에 가장 큰 제곱수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 지민이가 만든 수 중에 가장 큰 제곱수를 출력한다. 만약 제곱수가 없다면 -1을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int arr[10][10];
int isSquareNum(int n) {
for (int i = 0; i * i <= n; i++)
if (i * i == n)
return n;
return -1;
}
int main() {
int n, m, num, ans = -1;
int y, x, moveY, moveX;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%1d", &arr[i][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans = max(ans, isSquareNum(arr[i][j]));
for (moveY = 1 - i; moveY <= n - i; moveY++) {
for (moveX = 1 - j; moveX <= m - j; moveX++) {
if (moveY == 0 && moveX == 0)
continue;
num = 0;
y = i, x = j;
while (1 <= y && y <= n && 1 <= x && x <= m) {
num = num * 10 + arr[y][x];
ans = max(ans, isSquareNum(num));
y += moveY, x += moveX;
}
}
}
}
}
printf("%d\n", ans);
return 0;
}
|
cs |
완전 탐색을 이용해서 풀었다.
moveY와 moveX가 모두 0일때 무한루프에 빠지기 때문에 그 부분은 continue를 사용해서 처리했다.
그러다 보니까 n=1, m=1인 경우에 한 자리 제곱수를 잡아내지 못하는 문제가 있어서 24번째 줄에서 따로 처리했다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 16397 탈출 (0) | 2021.02.25 |
|---|---|
| 백준 온라인 저지 20951 유아와 곰두리차 (0) | 2021.02.23 |
| 백준 온라인 저지 17836 공주님을 구해라! (0) | 2021.02.15 |
| 백준 온라인 저지 12789 도키도키 간식드리미 (0) | 2021.02.10 |
| 백준 온라인 저지 1744 수 묶기 (0) | 2021.02.06 |
