시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 7643 | 2650 | 2101 | 34.163% |
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
2 3 123 456
64
만들 수 있는 세자리 수는 123, 321, 456, 654이다. 이 중 완전 제곱수는 없기 때문에 정답은 64가 된다.
5 5 00000 00000 00200 00000 00000
0
0은 완전 제곱수이고, 입력으로 주어진 표에서 만들 수 있는 가장 큰 완전 제곱수이다.
6 7 3791178 1283252 4103617 8233494 8725572 2937261
320356
모든 i번 행의 i번 열에 적힌 수를 이어붙이면 320356을 만들 수 있고, 이 수는 5662 = 320356 이다.
5 9 135791357 357913579 579135791 791357913 913579135
9
홀수 숫자 두 개로 끝나는 완전 제곱수는 없다. 따라서, 만들 수 있는 가장 큰 완전 제곱수는 9이다.
9 9 553333733 775337775 777537775 777357333 755553557 355533335 373773573 337373777 775557777
-1
3, 5, 7만을 이용해 완전 제곱수를 만들 수 없다.
9 9 257240281 197510846 014345401 035562575 974935632 865865933 684684987 768934659 287493867
95481
다음과 같이 굵게 표시된 숫자를 이어붙이면 95481을 만들 수 있다.
257240281 197510846 014345401 035562575 974935632 865865933 684684987 768934659 287493867